Submission #209570

#	Time	Username	Problem	Language	Result	Execution time	Memory
209570		DodgeBallMan	Examination (JOI19_examination)	C++14	0 / 100	123 ms	11236 KiB

examination

#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second 

using namespace std;

const int N = 10;

struct qq {
    int a, b, c, i;
    qq( int a, int b, int c, int i ) : a( a ), b( b ), c( c ), i( i ) {}
    friend bool operator<( const qq &a, const qq &b ) {
        return a.c > b.c;
    }
};
vector<qq> que;
vector<int> coord[N], t[N], coo;
vector<pii> sc;
int n, Q, ptr, ans[N];

void update( vector<int> &t, int idx ) {
    for( int i = idx ; i < t.size() ; i += i & -i ) t[i] += 1;
}

int query( vector<int> &t, int idx ) {
    int ret = 0;
    for( int i = idx ; i > 0 ; i -= i & -i ) ret += t[i];
    return ret;
}

int query2d( int x, int y ) {
    int ret = 0;
    for( int i = x ; i > 0 ; i -= i & -i ) {
        int idx = upper_bound( coord[i].begin(), coord[i].end(), y ) - coord[i].begin();
        int a = query( t[i], idx );
        //printf("QUERY : i%d x%d y%d a%d idx%d\n",i,x,y,a,idx);
        ret += query( t[i], idx );
    }
    return ret;
}

void update2d( int x, int y ) {
    for( int i = x ; i < N ; i += i & -i ) {
        int idx = upper_bound( coord[i].begin(), coord[i].end(), y ) - coord[i].begin();
        //printf("UPDATE : i%d x%d y%d idx%d\n",i,x,y,idx);
        update( t[i], idx );
    }
}

int get( int x ) { return lower_bound( coo.begin(), coo.end(), x ) - coo.begin() + 1; }
int main()
{
    scanf("%d %d",&n,&Q);
    for( int i = 0, a, b ; i < n ; i++ ) {
        scanf("%d %d",&a,&b);
        sc.emplace_back( pii( a, b ) ), coo.emplace_back( a );
    }
    sort( coo.begin(), coo.end() );
    coo.resize( unique( coo.begin(), coo.end() ) - coo.begin() );
    //printf("sz%d\n",coo.size());
    for( pii x : sc ) {
        int idx = get( x.x );
        for( int i = idx ; i < N ; i += i & -i ) {
            //printf("%d %d %d\n",get(x.x),i,x.y);
            coord[i].emplace_back( x.y );
        }
    }
    for( int i = 1 ; i < N ; i++ ) {
        sort( coord[i].begin(), coord[i].end() );
        coord[i].resize( unique( coord[i].begin(), coord[i].end() ) - coord[i].begin() );
        //printf("coord[%d] : ",i);
        //for( int j : coord[i] ) printf("%d ",j);
        //printf("\n");
        t[i].resize( coord[i].size() + 5 );
    }
    sort( sc.begin(), sc.end(), [&](pii &a, pii &b) {
        return a.x + a.y > b.x + b.y;
    });
    for( int i = 0, a, b, c ; i < Q ; i++ ) {
        scanf("%d %d %d",&a,&b,&c);
        que.emplace_back( a, b, c, i );
    }
    sort( que.begin(), que.end() );
    //printf("%d\n",coo.size());
    for( qq q : que ) {
        while( ptr < sc.size() && sc[ptr].x + sc[ptr].y >= q.c ) {
            update2d( get( sc[ptr].x ), sc[ptr].y );
            ptr++;
        }
        //printf("all : %d %d %d %d\n",query2d( coo.size(), 1e9 ),query2d( coo.size(), q.b-1 ),query2d( get( q.a ) - 1, 1e9 ), query2d( get( q.a )-1, q.b-1 ));
        ans[q.i] = query2d( coo.size(), 1e9 ) - query2d( coo.size(), q.b-1 ) - query2d( get( q.a ) - 1, 1e9 ) + query2d( get( q.a )-1, q.b-1 );
    }
    for( int i = 0 ; i < Q ; i++ ) printf("%d\n",ans[i]);
    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'void update(std::vector<int>&, int)':
examination.cpp:23:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for( int i = idx ; i < t.size() ; i += i & -i ) t[i] += 1;
                        ~~^~~~~~~~~~
examination.cpp: In function 'int query2d(int, int)':
examination.cpp:36:13: warning: unused variable 'a' [-Wunused-variable]
         int a = query( t[i], idx );
             ^
examination.cpp: In function 'int main()':
examination.cpp:87:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while( ptr < sc.size() && sc[ptr].x + sc[ptr].y >= q.c ) {
                ~~~~^~~~~~~~~~~
examination.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&Q);
     ~~~~~^~~~~~~~~~~~~~~
examination.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~~
examination.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&a,&b,&c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57