QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#100412#4219. InsectscrashedWA 2ms3376kbC++143.4kb2023-04-25 21:33:062023-04-25 21:33:10

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-25 21:33:10]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 3376kb
  • [2023-04-25 21:33:06]
  • Submitted

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 :: multiset<std :: pair<int, int> > s;
int BIT[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];
        if( cur > N ) 
            s.insert( { pnt[cur].second, pnt[cur].first } );
        else {
            auto it = s.lower_bound( { pnt[cur].second, 0 } );
            if( it != s.end() ) s.erase( it );
        }
    }
    std :: vector<Point> stk;
    std :: vector<int> blkL, blkR, whtL, whtR;
    for( auto it = s.rbegin() ; it != s.rend() ; it ++ )
        if( stk.empty() || stk.back().first < it -> second )
            stk.push_back( { it -> second, it -> first } );
    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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3376kb

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
4

result:

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