QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#100404#4219. InsectscrashedWA 2ms3388kbC++143.5kb2023-04-25 20:57:452023-04-25 20:57:48

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 20:57:48]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3388kb
  • [2023-04-25 20:57:45]
  • 提交

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<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( N + wL <= wht[i] && 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();
    std :: vector<Point> stk;
    per( i, tot, 1 ) {
        int cur = buf[i];
        if( cur > N ) {
            if( stk.empty() || stk.back().second < pnt[cur].second )
                stk.push_back( pnt[cur] );
            s.insert( pnt[cur].second );
        } else {
            auto it = s.lower_bound( pnt[cur].second );
            if( it != s.end() ) s.erase( it );
            if( s.empty() ) stk.clear();
            else {
                while( ! stk.empty() && stk.back().second > *s.rbegin() )
                    stk.pop_back();
            }
        }
    }
    std :: reverse( stk.begin(), stk.end() );

    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: 0
Wrong Answer
time: 2ms
memory: 3388kb

input:

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

output:

1
2
3
4

result:

wrong answer 3rd numbers differ - expected: '2', found: '3'