QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#100334#4219. InsectscrashedWA 2ms3884kbC++141.9kb2023-04-25 17:07:392023-04-25 17:07:41

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-25 17:07:41]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3884kb
  • [2023-04-25 17:07:39]
  • 提交

answer

#include <bits/stdc++.h>

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

const int MAXN = 1e5 + 10;

template<typename _T>
inline void Read( _T &x ) {
    x = 0; char s = getchar(); bool f = false;
    while( s < '0' || '9' < s ) { f = s == '-', s = getchar(); }
    while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
    if( f ) x = -x;
}

template<typename _T>
inline void Write( _T x ) {
    if( x < 0 ) putchar( '-' ), x = -x;
    if( 9 < x ) Write( x / 10 );
    putchar( x % 10 + '0' );
}

typedef std :: pair<int, int> Point;

Point blk[MAXN], wht[MAXN];

int lim[MAXN];

int N, M;

int main() {
    const int D = 1e5 + 1;

    Read( N );
    rep( i, 1, N ) {
        Read( blk[i].first ), Read( blk[i].second );
        blk[i].first ++, blk[i].second ++;
    }
    Read( M );
    rep( i, 1, M ) {
        Read( wht[i].first ), Read( wht[i].second );
        wht[i].first ++, wht[i].second ++;
    }
    rep( i, 1, D ) lim[i] = 0;
    int res = 0;
    rep( i, 1, M ) {
        if( lim[wht[i].first] >= wht[i].second )
            res ++;
        else {
            int tmp = 0;
            int xR = wht[i].first, xL = xR, yR = wht[i].second;
            while( xL > 1 && lim[xL - 1] < yR ) xL --;
            rep( j, 1, N ) 
                tmp -= xL <= blk[j].first && blk[j].first <= xR &&
                       lim[blk[j].first] < blk[j].second && blk[j].second <= yR;
            rep( j, 1, i )
                tmp += xL <= wht[j].first && wht[j].first <= xR &&
                       lim[wht[j].first] < wht[j].second && wht[j].second <= yR;
            if( tmp > 0 ) {
                res += tmp;
                rep( j, xL, xR ) lim[j] = yR;
            }
        }
        Write( i - res ), putchar( '\n' );
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3884kb

input:

3
0 0
1 1
2 2
4
0 0
1 1
0 0
3 3

output:

1
2
2
3

result:

ok 4 number(s): "1 2 2 3"

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 3688kb

input:

9
22 44
7 6
10 48
46 20
21 35
33 16
36 41
29 4
45 22
7
46 39
44 32
1 48
43 19
28 34
8 48
15 18

output:

1
2
2
3
4
5
6

result:

wrong answer 6th numbers differ - expected: '4', found: '5'