oj.uz

Submission #209571

# Submission time Handle Problem Language Result Execution time Memory
209571 2020-03-14T16:48:53 Z DodgeBallMan Examination (JOI19_examination) C++14
100 / 100
 724 ms 29412 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second 

using namespace std;

const int N = 1e5 + 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

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
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8056 KB Output is correct
2 Correct 13 ms 8184 KB Output is correct
3 Correct 14 ms 8184 KB Output is correct
4 Correct 14 ms 8184 KB Output is correct
5 Correct 14 ms 8184 KB Output is correct
6 Correct 14 ms 8184 KB Output is correct
7 Correct 31 ms 8800 KB Output is correct
8 Correct 28 ms 8824 KB Output is correct
9 Correct 27 ms 8828 KB Output is correct
10 Correct 22 ms 8696 KB Output is correct
11 Correct 24 ms 8824 KB Output is correct
12 Correct 20 ms 8572 KB Output is correct
13 Correct 31 ms 8824 KB Output is correct
14 Correct 27 ms 8824 KB Output is correct
15 Correct 27 ms 8824 KB Output is correct
16 Correct 23 ms 8824 KB Output is correct
17 Correct 21 ms 8696 KB Output is correct
18 Correct 18 ms 8568 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 20940 KB Output is correct
2 Correct 658 ms 23524 KB Output is correct
3 Correct 707 ms 23520 KB Output is correct
4 Correct 318 ms 20196 KB Output is correct
5 Correct 428 ms 24936 KB Output is correct
6 Correct 178 ms 20320 KB Output is correct
7 Correct 558 ms 23396 KB Output is correct
8 Correct 587 ms 23400 KB Output is correct
9 Correct 511 ms 23400 KB Output is correct
10 Correct 354 ms 25440 KB Output is correct
11 Correct 235 ms 19180 KB Output is correct
12 Correct 129 ms 20320 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 20940 KB Output is correct
2 Correct 658 ms 23524 KB Output is correct
3 Correct 707 ms 23520 KB Output is correct
4 Correct 318 ms 20196 KB Output is correct
5 Correct 428 ms 24936 KB Output is correct
6 Correct 178 ms 20320 KB Output is correct
7 Correct 558 ms 23396 KB Output is correct
8 Correct 587 ms 23400 KB Output is correct
9 Correct 511 ms 23400 KB Output is correct
10 Correct 354 ms 25440 KB Output is correct
11 Correct 235 ms 19180 KB Output is correct
12 Correct 129 ms 20320 KB Output is correct
13 Correct 700 ms 23912 KB Output is correct
14 Correct 690 ms 23912 KB Output is correct
15 Correct 676 ms 23528 KB Output is correct
16 Correct 312 ms 20580 KB Output is correct
17 Correct 441 ms 25572 KB Output is correct
18 Correct 223 ms 20192 KB Output is correct
19 Correct 724 ms 23908 KB Output is correct
20 Correct 690 ms 23908 KB Output is correct
21 Correct 670 ms 23904 KB Output is correct
22 Correct 363 ms 25440 KB Output is correct
23 Correct 245 ms 19172 KB Output is correct
24 Correct 129 ms 20328 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8056 KB Output is correct
2 Correct 13 ms 8184 KB Output is correct
3 Correct 14 ms 8184 KB Output is correct
4 Correct 14 ms 8184 KB Output is correct
5 Correct 14 ms 8184 KB Output is correct
6 Correct 14 ms 8184 KB Output is correct
7 Correct 31 ms 8800 KB Output is correct
8 Correct 28 ms 8824 KB Output is correct
9 Correct 27 ms 8828 KB Output is correct
10 Correct 22 ms 8696 KB Output is correct
11 Correct 24 ms 8824 KB Output is correct
12 Correct 20 ms 8572 KB Output is correct
13 Correct 31 ms 8824 KB Output is correct
14 Correct 27 ms 8824 KB Output is correct
15 Correct 27 ms 8824 KB Output is correct
16 Correct 23 ms 8824 KB Output is correct
17 Correct 21 ms 8696 KB Output is correct
18 Correct 18 ms 8568 KB Output is correct
19 Correct 644 ms 20940 KB Output is correct
20 Correct 658 ms 23524 KB Output is correct
21 Correct 707 ms 23520 KB Output is correct
22 Correct 318 ms 20196 KB Output is correct
23 Correct 428 ms 24936 KB Output is correct
24 Correct 178 ms 20320 KB Output is correct
25 Correct 558 ms 23396 KB Output is correct
26 Correct 587 ms 23400 KB Output is correct
27 Correct 511 ms 23400 KB Output is correct
28 Correct 354 ms 25440 KB Output is correct
29 Correct 235 ms 19180 KB Output is correct
30 Correct 129 ms 20320 KB Output is correct
31 Correct 700 ms 23912 KB Output is correct
32 Correct 690 ms 23912 KB Output is correct
33 Correct 676 ms 23528 KB Output is correct
34 Correct 312 ms 20580 KB Output is correct
35 Correct 441 ms 25572 KB Output is correct
36 Correct 223 ms 20192 KB Output is correct
37 Correct 724 ms 23908 KB Output is correct
38 Correct 690 ms 23908 KB Output is correct
39 Correct 670 ms 23904 KB Output is correct
40 Correct 363 ms 25440 KB Output is correct
41 Correct 245 ms 19172 KB Output is correct
42 Correct 129 ms 20328 KB Output is correct
43 Correct 672 ms 26468 KB Output is correct
44 Correct 685 ms 26340 KB Output is correct
45 Correct 666 ms 26344 KB Output is correct
46 Correct 343 ms 22372 KB Output is correct
47 Correct 477 ms 28516 KB Output is correct
48 Correct 186 ms 20196 KB Output is correct
49 Correct 569 ms 26216 KB Output is correct
50 Correct 619 ms 26088 KB Output is correct
51 Correct 540 ms 26088 KB Output is correct
52 Correct 391 ms 29412 KB Output is correct
53 Correct 265 ms 20320 KB Output is correct