QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#100412 | #4219. Insects | crashed | WA | 2ms | 3376kb | C++14 | 3.4kb | 2023-04-25 21:33:06 | 2023-04-25 21:33:10 |
Judging History
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'