QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#100416 | #4219. Insects | crashed | WA | 2ms | 5472kb | C++14 | 3.7kb | 2023-04-25 22:09:38 | 2023-04-25 22:09:41 |
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 :: 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.lower_bound( { pnt[cur].second, 0 } );
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: 0ms
memory: 3412kb
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: 3320kb
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: 3456kb
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: 2ms
memory: 3324kb
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: 2ms
memory: 3324kb
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: 1ms
memory: 3352kb
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: 0ms
memory: 3316kb
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: 3356kb
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: 1ms
memory: 5472kb
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: 5464kb
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: 2ms
memory: 3360kb
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: 5400kb
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'