Cerinta completa

In a galaxy far away, there is a constant battle between the republic and the droid army. The droid army decided to launch their final attack on the republic. They have N space-fighters.

Initially the ith fighter is located at (xi, yi). All of the space-fighters move with constant velocity V units/sec in the positive X direction.
i.e., fighter at (xi, yi) moves to (xi+V, yi) in 1 second.
The ith space-fighter broadcasts enemy information at a frequency fi.

The republic is not scared of the artificially intelligent droid force as they have Yoda. Yoda has a special power, at any time T he can choose a region of the droid army and block one specific frequency F. This power has one constraint; it can be applied only in the form of a two sided unbounded axis parallel rectangular box open towards the both the directions across X axis (refer image below for clarity). If a frequency (F) is blocked all the space-fighters in the region having the frequency F can’t communicate.

starfleet

Given the initial positions of the space-fighters, and their velocity, you are to answer queries of the following form:

YU YD T

where YU, YD are the bounds on y-axis inside which YODA can block a frequency at time T.
In the region described by the query, after a time T seconds from the start, if Yoda can chose one frequency (F) he wishes to, what is the maximum number of communications he can block?

Input Format
Each test case is described as follows; the first line contains 3 space separated integers N – the number of space-fighters, Q – the number of queries you have to answer, and V – the velocity of the space-fighters separated by a single space.

N lines follow, each containing 3 space separated integers xi, yi, and fi, denoting the x co-ordinate, y co-ordinate and the frequency at which the ith ship broadcasts respectively. Each of the next Q lines contain 3 space separated integers representing YU, YD, T respectively. Refer the figure for more clarity

Note: Points on the boundaries should be counted as well.

Output Format
For each query you are to output a single integer denoting the result.

Constraints
1 <= N <= 50000
1 <= Q <= 30000
1 <= V <= 10000
-109 <= xi <= 109
-109 <= yi <= 109
1 <= fi <= 109
-109 <= YU <= 109
-109 <= YD <= 109
1 <= T <= 10000
YU >= YD

Sample Input

5 5 82
-4 1 4
-3 -2 2
-3 5 1
0 -5 2
1 -1 2
1 -1 57
-2 -5 11
5 -5 40
-1 -5 16
5 -1 93

Sample Output

1
2
3
3
1

Explanation
Consider the points ships in the Y-range 1 to -1, they are the (-4, 1) and (1, -1), and both operate on different frequencies, hence the most times a frequency is repeated is once.

Limbajul de programare folosit: cpp14

Cod:

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <cmath>
#include <ctime>
#include <queue>
#include <list>
#include <map>
#include <set>

#define For(i,a,b) for(register int (i)=(a);(i)<=(b);(i)++)
#define FOR(i,a) For(i,1,a)
#define Ford(i,a,b) for(register int (i)=(a);(i)>=(b);(i)--)
#define Rep(i,a,b) for(register int (i)=(a);(i)<(b);(i)++)
#define REP(i,a) Rep(i,0,a)
#define type(x) __typeof(x.begin())
#define foreach(it,x) for(__typeof(x.begin()) it = x.begin() ; it!=x.end() ; it++ )

#define NEW(x,n) (x*)calloc(n,sizeof(x))
#define fill(x,y) memset(x,y,sizeof x)
#define all(x) x.begin(),x.end()
#define compress(x) {sort(all(x));(x).resize(unique(all(x))-(x).begin());}
#define two(x) (1LL<<(x))
#define fi first
#define se second
#define gcd __gcd
#define pb push_back
#define mp make_pair

#ifdef KAZAR
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
    #define dbg(x) cerr<<#x<<":"<<(x)<<endl
    #define dg(x) cerr<<#x<<":"<<(x)<<' '
#else
    #define eprintf(...) 0
    #define dbg(x) 0
    #define dg(x) 0
#endif

using namespace std;

typedef long long Lint;
typedef long double ld;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;

const int inf = 1e9+5143;
const Lint Linf = 1e18+5413;
const double eps = 1e-15;
const double pi = acos(-1);

template<class T> inline void umax(T &a,T b){if(a<b) a = b ; }
template<class T> inline void umin(T &a,T b){if(a>b) a = b ; }
template<class T> inline T abs(T a){return a>0 ? a : -a;}
template<class T> inline T lcm(T a,T b){
    return a/gcd(a,b)*b;
}

inline int read(){
    int res = 0LL ;int neg ;
    while(1){
        char ch = getchar();
        if(ch>='0' && ch<='9' || ch=='-'){
            if(ch=='-') neg = -1;
            else neg = 1 , res = ch-'0';
            break;
        }
    }
    while(1){
        char ch = getchar();
        if(ch>='0' && ch<='9') res*=10 , res+=ch-'0';
        else break;
    }
    return res*neg;
}

const int N = 492717;
const int SQ = 300;

ii a[N];
int f[N];
vi valsx , vals;
vi occurance[N];
vii ask[N];
vi huges;
int ans[N];
int q;
vi here[N];

void get_damn_input(){

    int n = read();
    q = read();
    read();

    FOR(i,n){
        read();
        a[i].fi = read();
        a[i].se = read();
        valsx.pb(a[i].fi);
    }

    compress(valsx);

    FOR(i,n){
        a[i].fi = lower_bound(all(valsx),a[i].fi) - valsx.begin() + 1;
    }

    sort(a + 1,a + 1 + n);

    FOR(i,n){
        vals.pb(a[i].se);
    }

    compress(vals);

    FOR(i,n){
        f[i] = lower_bound(all(vals),a[i].se) - vals.begin() + 1;
        assert(f[i] < N);
        occurance[f[i]].pb(a[i].fi);
        assert(a[i].fi < N);
        here[a[i].fi].pb(f[i]);
    }

    REP(i,N) compress(here[i]);

    REP(i,vals.size() + 5){
        sort(all(occurance[i]));
        if(occurance[i].size() > SQ){
            huges.pb(i);
        }
    }

    FOR(i,q){
        int r = upper_bound(all(valsx),read()) - valsx.begin();
        int l = lower_bound(all(valsx),read()) - valsx.begin() + 1;
        read();
        eprintf("query %d , %dn",l,r);
        assert(r < N);
        ask[r].pb(ii(l,i));
    }

}

int kd[N * 10];

void put(int k,int b,int e,int x,int val){
    assert(k < N * 10);
    if(b > x || e < x) return;
    if(b == e){
        assert(val > 0);
        umax(kd[k],val);
        return;
    }
    put(k + k,b,(b+e)/2,x,val);
    put(k + k + 1,(b+e)/2 + 1,e,x,val);
    kd[k] = max(kd[k + k],kd[k + k + 1]);
}

int get(int k,int b,int e,int x1,int x2){
    assert(k < N * 10);
    if(b > x2 || e < x1) return 0;
    if(b >= x1 && e <= x2) return kd[k];
    return max(get(k + k,b,(b+e)/2,x1,x2),get(k + k + 1,(b+e)/2+1,e,x1,x2));
}

void insert(int idx,int where){
    assert(idx < N);
    if(occurance[idx].size() > SQ) return;
    int cur = 0;
    Ford(i,occurance[idx].size() - 1,0){
        if(occurance[idx][i] <= where){
            put(1,1,N,occurance[idx][i],++cur);
        }
    }
}

int main(){

#ifdef KAZAR
    freopen("f.input","r",stdin);
    freopen("f.output","w",stdout);
    freopen("error","w",stderr);
#endif
    
    get_damn_input();

    REP(i,10){
        eprintf("here %d: ",i);
        foreach(it,here[i]) eprintf("%d ",*it);
        eprintf("n");
    }

    dbg(huges.size());

    REP(i,N){
        assert(i < N);
        foreach(it,here[i]){
            insert(*it,i);
            eprintf("inserting i:%d f:%d then : %dn",i,*it,get(1,1,N,1,i));
        }
        int r = i;
        foreach(it,ask[r]){
            int l = it->fi;
            assert(l < N);
            assert(r < N);
            int res = get(1,1,N,l,r);
            foreach(huge,huges){
                assert(*huge < N);
                umax(res,int(upper_bound(all(occurance[*huge]),r) - lower_bound(all(occurance[*huge]),l)) );
            }
            ans[it->se] = res;
        }
    }

    FOR(i,q) printf("%d\n",ans[i]);

    return 0;
}

Scor obtinut: 1.0

Submission ID: 464653656

Link challenge: https://www.hackerrank.com/challenges/starfleet/problem

Starfleet