QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#100417#4219. InsectscrashedWA 2ms3472kbC++143.7kb2023-04-25 22:17:542023-04-25 22:17:57

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 22:17:57]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3472kb
  • [2023-04-25 22:17:54]
  • 提交

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 = 2e5 + 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;

std :: set<std :: pair<int, int> > s;
int BIT[MAXN], succ[MAXN];

Point pnt[MAXN];
int buf[MAXN];

int ans[MAXN];

int N, M;

inline void Down( int &x ) { x &= x - 1; }
inline void Up( int &x ) { x += x & ( - x ); }
inline void Update( int x, int v ) { for( ; x <= M ; Up( x ) ) BIT[x] += v; }
inline  int Query( int x ) { int ret = 0; for( ; x ; Down( x ) ) ret += BIT[x]; return ret; }

void Divide( const std :: vector<int> &blk, const std :: vector<int> &wht,
             const int &wL, const int &wR, const int &su ) {
    if( wL > wR ) return ;
    int n = blk.size(), m = wht.size();
    int mid = ( wL + wR ) >> 1, tot = 0;
    rep( i, 0, n - 1 ) buf[++ tot] = blk[i];
    rep( i, 0, m - 1 ) 
        if( wht[i] <= N + mid )
            buf[++ tot] = wht[i];
    std :: sort( buf + 1, buf + 1 + tot,
        [] ( const int &a, const int &b ) -> bool {
            return pnt[a] == pnt[b] ? a < b : pnt[a] < pnt[b];
        } );

    s.clear();
    per( i, tot, 1 ) {
        int cur = buf[i]; succ[cur] = 0;
        if( cur > N ) {
            auto it = s.upper_bound( { pnt[cur].second, N + 1 } );
            if( it != s.begin() ) succ[cur] = ( -- it ) -> second;
            s.insert( { pnt[cur].second, cur } );
        } else {
            auto it = s.lower_bound( { pnt[cur].second, 0 } );
            if( it != s.end() ) s.erase( it );
        }
    }
    std :: vector<Point> stk;
    if( ! s.empty() )
        for( int x = s.rbegin() -> second ; x ; x = succ[x] )
            stk.push_back( pnt[x] );
    // std :: vector<Point> stk;
    // for( auto it = s.rbegin() ; it != s.rend() ; it ++ )
    //     if( stk.empty() || stk.back().first < it -> second )
    //         stk.push_back( { it -> second, it -> first } );

    std :: vector<int> blkL, blkR, whtL, whtR;
    for( const int &cur : blk ) {
        auto it = std :: lower_bound( stk.begin(), stk.end(), Point( pnt[cur].first, 0 ) );
        if( it != stk.end() && it -> second >= pnt[cur].second )
            blkL.push_back( cur );
        else blkR.push_back( cur );
    }
    for( const int &cur : wht ) {
        auto it = std :: lower_bound( stk.begin(), stk.end(), Point( pnt[cur].first, 0 ) );
        if( it != stk.end() && it -> second >= pnt[cur].second )
            whtL.push_back( cur );
        else whtR.push_back( cur );
    }
    Divide( blkL, whtL, wL, mid - 1, su );
    for( const int &x : whtL ) Update( x - N, +1 );
    ans[mid] = su - blkL.size() + Query( mid );
    Divide( blkR, whtR, mid + 1, wR, su - blkL.size() );
    for( const int &x : whtL ) Update( x - N, -1 );
}

int main() {
    Read( N );
    rep( i, 1, N )
        Read( pnt[i].first ), Read( pnt[i].second );
    Read( M );
    rep( i, 1, M )
        Read( pnt[i + N].first ), Read( pnt[i + N].second );
    std :: vector<int> blk( N ), wht( M );
    rep( i, 1, N ) blk[i - 1] = i;
    rep( i, 1, M ) wht[i - 1] = i + N;
    Divide( blk, wht, 1, M, 0 );
    rep( i, 1, M ) Write( i - ans[i] ), putchar( '\n' );
    return 0;
}

詳細信息

Test #1:

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

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: 0
Accepted
time: 2ms
memory: 3324kb

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
4
4

result:

ok 7 numbers

Test #3:

score: 0
Accepted
time: 2ms
memory: 3424kb

input:

7
25 13
38 45
30 28
28 29
16 34
45 4
47 13
8
24 16
10 18
8 28
40 47
28 35
5 25
29 0
41 17

output:

0
0
0
1
2
2
2
3

result:

ok 8 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 3388kb

input:

10
47 32
0 16
18 11
17 19
40 49
36 24
3 26
15 45
23 29
42 3
5
42 18
22 3
30 13
35 19
43 29

output:

1
1
2
3
4

result:

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

Test #5:

score: 0
Accepted
time: 0ms
memory: 3384kb

input:

6
2 5
22 3
28 41
41 36
9 8
8 17
2
24 7
49 35

output:

1
2

result:

ok 2 number(s): "1 2"

Test #6:

score: 0
Accepted
time: 2ms
memory: 3332kb

input:

2
27 36
5 39
6
47 22
45 4
44 2
24 2
29 11
21 37

output:

0
0
0
0
0
0

result:

ok 6 numbers

Test #7:

score: 0
Accepted
time: 2ms
memory: 3464kb

input:

30
35 14
26 38
50 17
21 0
14 0
39 2
5 45
1 18
22 50
5 49
35 16
37 43
15 11
22 16
4 9
44 36
1 23
42 19
33 44
2 44
35 16
21 36
23 46
39 1
15 29
9 17
31 27
37 50
15 24
30 38
48
10 38
28 0
33 5
33 11
36 27
4 30
4 18
23 28
4 8
16 20
24 47
14 34
30 45
47 10
4 48
36 2
10 20
11 39
49 39
11 50
48 36
28 41
23...

output:

1
2
3
4
5
6
7
8
8
9
10
10
11
12
13
13
13
13
14
15
16
17
17
17
18
18
19
20
21
22
23
23
23
23
23
23
24
24
24
24
25
25
25
25
26
26
26
26

result:

ok 48 numbers

Test #8:

score: 0
Accepted
time: 2ms
memory: 3472kb

input:

38
13 24
34 6
36 39
31 36
25 23
32 37
20 37
34 18
38 22
37 11
42 50
30 44
1 2
7 41
17 14
31 25
31 37
7 32
46 12
18 46
22 36
18 20
21 9
46 44
39 26
24 34
42 17
38 22
16 35
0 50
24 28
8 45
44 40
2 46
37 35
28 20
22 29
31 32
2
45 4
27 6

output:

1
1

result:

ok 2 number(s): "1 1"

Test #9:

score: 0
Accepted
time: 2ms
memory: 3416kb

input:

8
20 46
34 26
11 23
40 29
21 9
48 13
10 47
4 28
30
22 34
8 23
21 9
31 1
44 27
9 12
48 17
43 24
17 15
48 8
22 5
27 26
46 27
42 0
14 28
9 34
5 2
8 29
26 7
13 3
44 19
50 7
40 29
43 31
49 31
50 26
20 19
2 10
39 25
41 0

output:

1
1
2
2
3
3
4
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
6

result:

ok 30 numbers

Test #10:

score: 0
Accepted
time: 2ms
memory: 3444kb

input:

14
47 8
17 15
15 9
0 17
12 27
44 31
42 44
16 11
22 1
12 49
31 24
0 6
41 24
46 12
11
48 10
20 23
39 6
39 34
31 44
16 49
50 8
48 22
22 29
36 22
12 20

output:

1
2
3
4
5
6
7
8
9
10
11

result:

ok 11 numbers

Test #11:

score: 0
Accepted
time: 1ms
memory: 3384kb

input:

30
33 49
47 40
4 49
33 30
9 0
16 12
26 7
25 25
44 40
2 19
31 37
6 11
21 46
42 16
25 8
15 11
42 24
14 44
23 16
48 30
24 39
32 50
14 9
49 22
29 5
24 49
37 1
7 13
20 25
8 17
24
31 18
20 1
7 21
4 34
10 10
39 43
16 5
27 26
40 19
36 14
18 12
34 12
49 5
4 39
3 38
7 15
18 44
26 33
13 5
13 14
34 49
28 27
23 ...

output:

1
2
3
4
4
5
5
6
7
8
9
10
11
11
11
12
13
14
14
14
15
16
17
18

result:

ok 24 numbers

Test #12:

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

input:

15
16 10
40 44
4 27
29 24
47 11
37 9
28 19
21 47
47 49
34 4
1 20
28 32
42 28
28 3
46 33
30
8 14
36 37
4 13
6 26
2 23
33 43
0 6
27 34
0 0
17 38
50 35
7 28
7 0
33 49
23 0
45 29
47 5
23 42
45 14
25 1
5 40
35 37
32 35
12 1
16 32
32 26
47 32
15 25
40 40
20 34

output:

0
1
1
2
2
3
3
4
4
5
6
6
6
7
7
8
9
9
10
10
10
11
12
12
12
13
14
13
13
13

result:

wrong answer 26th numbers differ - expected: '12', found: '13'