QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#100410 | #4219. Insects | crashed | WA | 2ms | 3392kb | C++14 | 3.5kb | 2023-04-25 21:00:16 | 2023-04-25 21:00:23 |
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<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();
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: 100
Accepted
time: 2ms
memory: 3384kb
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: 1ms
memory: 3392kb
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: 3384kb
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: -100
Wrong Answer
time: 2ms
memory: 3380kb
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 2 3 4 5
result:
wrong answer 2nd numbers differ - expected: '1', found: '2'