ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#194716 | #2038. b | snow_trace | 100 | 2123ms | 34252kb | C++11 | 2.3kb | 2023-10-17 09:46:35 | 2023-10-17 12:03:46 |
answer
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
vector<int>p1,p2;
int tag = 0;
int n;
int k[1000005],a[1000005],tree1[1000005],tree2[1000005];
void upd1(int pos,int add){
assert(pos !=0);
for(int i =pos;i<=n;i+=lowbit(i))tree1[i]+=add;return;
}void upd2(int pos,int add){
//assert(pos!=0);
for(int i =pos;i<=n;i+=lowbit(i))tree2[i]+=add;return;
}int query1(int pos){int res = 0;
for(int i = pos;i>0;i-=lowbit(i))res+=tree1[i];return res;
}int query2(int pos){int res =0;
for(int i = pos;i>0;i-=lowbit(i))res+=tree2[i];return res;
}inline int read(){
int x =0,f = 1;char c = getchar();
while(c<'0' or c>'9'){
if(c =='-')f= -1;
c = getchar();
}
while('0'<=c and c<='9'){
x = x*10+(c^48),c = getchar();
}return x*f;
}inline void write(int x){
if(x<0)putchar('-'),x = -x;
if(x>=10)write(x/10);
putchar('0'+x%10);
}int pos1[1000005],pos2[1000005];
vector<int>q;
signed main(){
//freopen("sth.out","w",stdout);
// srand(time(0));
// n = 1000000;
n = read();
for(int i = 1;i<=n;i++){
//k[i] = 1,a[i] = rand();
k[i] = read(),a[i]= read();k[i]^=1;
}//for(int i = 1;i<=n;i++)cout << k[i] << a[i];return 0;
for(int i = 1;i<=n;i++){
if(k[i]){
tag++;
p1.push_back(a[i]+tag),p2.push_back(a[i]);
}
}sort(p1.begin(),p1.end());p1.erase(unique(p1.begin(),p1.end()),p1.end());
sort(p2.begin(),p2.end());p2.erase(unique(p2.begin(),p2.end()),p2.end());
//return 0;
//assert(p1.size()<=n),assert(p2.size()<=n);
tag =0;q.push_back(0);
for(int i = 1;i<=n;i++){
if(k[i]){
tag++;q.push_back(i);
// cout << 111 << endl;
pos1[i] = n-(lower_bound(p1.begin(),p1.end(),a[i]+tag)-p1.begin());
pos2[i] = n-(lower_bound(p2.begin(),p2.end(),a[i])-p2.begin());
//cout << pos1[i] << " " << pos2[i] <<endl;
int res = query2(pos2[i])-query1(pos1[i]-1);
//cout << " " << query2(pos2[i]) << " " << query1(pos1[i]-1) << endl;
write(res);putchar('\n');
upd1(pos1[i],1),upd2(pos2[i],1);
}else{
//cout << 111 << endl;
upd1(pos1[q[a[i]]],-1),upd2(pos2[q[a[i]]],-1);
//cout << 111 << endl;
}
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 1ms
memory: 1236kb
input:
666 0 -389 0 -952 0 143 1 1 0 6 0 179 0 -923 0 -20 0 302 0 -109 1 8 0 894 0 -573 0 494 0 -385 0 -873...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 2 0 0 0 0 1 0 0 ...
result:
ok 593 numbers
Test #2:
score: 10
Accepted
time: 0ms
memory: 1240kb
input:
1000 0 588 1 1 0 -628 0 -956 0 -665 0 765 0 -190 0 -576 0 -813 0 -292 0 274 1 10 0 651 0 -205 0 -574...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 ...
result:
ok 888 numbers
Test #3:
score: 10
Accepted
time: 22ms
memory: 2764kb
input:
50000 0 -7094 0 -8664 0 -9115 1 3 0 -9755 0 -3119 0 4344 0 1734 1 5 0 -3462 1 7 0 7843 0 5728 0 -562...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 ...
result:
ok 44900 numbers
Test #4:
score: 10
Accepted
time: 28ms
memory: 3404kb
input:
70000 0 -5155 1 1 0 9088 0 6886 0 -5081 0 1938 0 -959 0 -8158 0 414 1 4 0 6503 0 2048 0 9571 0 -9902...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 63042 numbers
Test #5:
score: 10
Accepted
time: 33ms
memory: 3880kb
input:
85000 0 -8442 0 7059 0 2716 0 307 1 1 0 1173 0 -2796 1 2 0 -3617 0 5458 0 -1083 0 -3482 1 5 0 2832 0...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 76519 numbers
Test #6:
score: 10
Accepted
time: 50ms
memory: 4256kb
input:
100000 0 -3400 0 -3786 0 -4616 0 -3125 0 -3813 0 9233 1 1 0 32 0 -5027 0 -6531 0 -9932 0 -8502 0 -31...
output:
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 90009 numbers
Test #7:
score: 10
Accepted
time: 195ms
memory: 13000kb
input:
300000 0 -578222155 1 1 0 -464946128 0 -503954765 0 -579608591 0 -147391629 1 2 0 -140936373 1 4 0 -...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 270045 numbers
Test #8:
score: 10
Accepted
time: 366ms
memory: 17664kb
input:
500000 0 -879047197 0 22865740 0 -579471564 0 -455491333 0 -632783600 0 -345134153 0 -341714454 0 -7...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 450086 numbers
Test #9:
score: 10
Accepted
time: 550ms
memory: 27020kb
input:
700000 0 -106097647 0 -135803415 0 -694029768 0 -407027902 1 2 1 3 0 -534078466 0 -317401273 0 -2520...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 629728 numbers
Test #10:
score: 10
Accepted
time: 878ms
memory: 34252kb
input:
1000000 0 -759131017 0 -632412881 0 -712627012 0 -353714850 0 -207626084 0 -545766331 0 -423546500 0...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 899925 numbers
Extra Test:
score: 0
Extra Test Passed