UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#194716#2038. bsnow_trace1002123ms34252kbC++112.3kb2023-10-17 09:46:352023-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