QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#717206#8302. Incoming AsteroidsSouthern_DynastyAC ✓746ms189464kbC++173.5kb2024-11-06 17:13:482024-11-06 17:13:48

Judging History

你现在查看的是最新测评结果

  • [2024-11-06 17:13:48]
  • 评测
  • 测评结果:AC
  • 用时:746ms
  • 内存:189464kb
  • [2024-11-06 17:13:48]
  • 提交

answer

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define gt getchar
#define pt putchar
#define fst first
#define scd second
#define SZ(s) ((int)s.size())
#define all(s) s.begin(),s.end()
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int uint;
const int N=2e5+5;
using namespace std;
using namespace __gnu_pbds;
typedef pair<ll,int> pii;
template<class T,class I> inline bool chkmax(T &a,I b){return b>a?a=b,1:0;}
template<class T,class I> inline bool chkmin(T &a,I b){return b<a?a=b,1:0;}
inline bool __(char ch){return ch>=48&&ch<=57;}
template<class T> inline void read(T &x){
	x=0;bool sgn=0;static char ch=gt();
	while(!__(ch)&&ch!=EOF) sgn|=(ch=='-'),ch=gt();
	while(__(ch)) x=(x<<1)+(x<<3)+(ch&15),ch=gt();
	if(sgn) x=-x;
}
template<class T,class ...I> inline void read(T &x,I &...x1){
	read(x);
	read(x1...);
}
template<class T> inline void print(T x){
	static char stk[70];short top=0;
	if(x<0) pt('-');
	do{stk[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
	while(top) pt(stk[top--]);
}
template<class T> inline void printsp(T x){
	print(x);
	putchar(' ');
}
template<class T> inline void println(T x){
	print(x);
	putchar('\n');
}
int n,m,lst;
ll tag[N];// 减了多少.
struct Set{
	priority_queue<pii,vector<pii>,greater<pii> > pq1,pq2;
	inline void ins(pii x){pq1.push(x);}
	inline void del(pii x){pq2.push(x);}
	inline void adj(){while(SZ(pq2)&&pq1.top()==pq2.top()) pq1.pop(),pq2.pop();}
	inline int size(){return SZ(pq1)-SZ(pq2);}
	inline pii top(){adj();return pq1.top();} 
}st[N];
struct Node{
	int lim,k,vec[10];
	ll now[10];
	inline void input(){
		read(lim);
		lim^=lst;
		read(k);
		for(int i=1;i<=k;++i) read(vec[i]),vec[i]^=lst;
	}
	inline ll calc(){
		ll ans=0;
		for(int i=1;i<=k;++i) ans+=now[i]-tag[vec[i]];
		return ans;
	}
}node[N];
signed main(){
	read(n,m);
	int tot=0;
	for(int opt,x,y;m;--m){
		read(opt);
		if(opt==1){
			node[++tot].input();
			for(int i=1;i<=node[tot].k;++i){
				node[tot].now[i]=(node[tot].lim/node[tot].k);
			}
			for(int i=1;i<=node[tot].lim%node[tot].k;++i) node[tot].now[i]++;
			for(int i=1;i<=node[tot].k;++i){
				int id=node[tot].vec[i];
				node[tot].now[i]+=tag[id];
				st[id].ins(pii(node[tot].now[i],tot));
			}
		}else{
			read(x,y);
			x^=lst,y^=lst;
			tag[x]+=y;
			vector<int> ans;
			while(SZ(st[x])&&st[x].top().fst-tag[x]<=0){
				int u=st[x].top().scd,cur=node[u].calc();
				if(cur<=0){
					ans.eb(u);
					for(int i=1;i<=node[u].k;++i){
						int id=node[u].vec[i];
						st[id].del(pii(node[u].now[i],u));
					}
				}else{
					for(int i=1;i<=node[u].k;++i){
						int id=node[u].vec[i];
						st[id].del(pii(node[u].now[i],u));
					}
					for(int i=1;i<=node[u].k;++i) node[u].now[i]=cur/node[u].k;
					cur%=node[u].k;
					for(int i=1;i<=node[u].k&&cur;++i){
						if(node[u].vec[i]==x){
							node[u].now[i]++;
							cur--;
							break;
						}	
					}
					for(int i=1;i<=node[u].k&&cur;++i){
						if(node[u].vec[i]!=x){
							node[u].now[i]++;
							cur--;
						}
					}
					for(int i=1;i<=node[u].k;++i){
						int id=node[u].vec[i];
						node[u].now[i]+=tag[id];
						st[id].ins(pii(node[u].now[i],u));
					}
				}
			}
			sort(all(ans));
			lst=SZ(ans);
			print(lst);
			for(int v:ans) pt(' '),print(v);
			printf("\n");
		}
	}
	return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 17880kb

input:

3 5
1 5 3 1 2 3
2 2 1
1 2 2 1 2
2 3 1
2 1 3

output:

0
0
2 1 2

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 35ms
memory: 38440kb

input:

200000 200000
1 421386 1 122023
2 127573 97972
1 489180 1 197930
2 82505 59100
1 502097 3 91617 14193 139642
2 132931 74031
1 404862 1 36227
2 152826 8462
1 750072 2 51616 75416
2 1547 11479
1 255849 2 70036 41620
2 126414 17120
1 626334 3 97273 190595 174083
2 148803 132
1 407236 2 83898 5103
2 169...

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
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 lines

Test #3:

score: 0
Accepted
time: 37ms
memory: 36000kb

input:

200000 200000
1 312309 2 171927 138033
2 68663 9986
1 409422 3 107618 121948 134622
2 10082 2963
1 555050 1 90783
2 72655 3281
1 933143 3 156038 38059 61251
2 123654 4789
1 491632 2 22976 168618
2 156647 7902
1 389305 3 132923 162027 1538
2 123738 4011
1 362971 3 94150 50751 80442
2 52203 8937
1 205...

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
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 lines

Test #4:

score: 0
Accepted
time: 30ms
memory: 36956kb

input:

200000 200000
1 142543 1 115092
2 171364 77800
1 175929 3 183076 20412 144389
2 44523 136842
1 342332 3 155151 4240 89238
2 111001 39417
1 133140 2 69162 186231
2 170481 10806
1 680994 2 138407 7106
2 170161 198340
1 772506 1 109120
2 24352 199102
1 901774 2 114997 161429
2 74138 125234
1 757250 1 1...

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
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 lines

Test #5:

score: 0
Accepted
time: 42ms
memory: 41584kb

input:

20000 200000
1 678769 3 4395 16744 14145
2 8935 15738
1 432048 3 9768 6009 16504
2 12630 12968
1 397741 3 223 1836 378
2 257 18108
1 850814 3 4564 13454 7781
2 2124 13159
1 252004 3 15683 16496 18755
2 5458 25974
1 433880 3 5518 9833 9661
2 1925 405
1 892145 3 15731 16871 19282
2 17132 17115
1 81156...

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
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 lines

Test #6:

score: 0
Accepted
time: 106ms
memory: 41236kb

input:

4000 200000
1 302161 3 2309 1618 194
2 3316 19207
1 878861 3 2986 2907 146
2 3099 26347
1 932183 3 648 3750 1939
2 29 23023
1 327262 3 2959 548 986
2 3356 22562
1 542484 3 490 465 3590
2 3121 1669
1 246973 3 1328 3985 605
2 75 1839
1 392188 3 658 2867 1928
2 800 29554
1 315643 3 157 2426 331
2 600 1...

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
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 lines

Test #7:

score: 0
Accepted
time: 158ms
memory: 32920kb

input:

200 200000
1 44130 3 22 167 30
2 107 8878
1 391579 3 107 68 58
2 179 166
1 797413 3 85 145 186
2 128 18222
1 588792 3 78 104 10
2 168 5761
1 720090 3 33 198 62
2 26 16475
1 342624 3 49 94 153
2 34 4317
1 410548 3 197 166 55
2 124 8507
1 985428 3 1 158 126
2 174 14078
1 32984 3 112 126 55
2 59 15762
...

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
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 105
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 lines

Test #8:

score: 0
Accepted
time: 158ms
memory: 30960kb

input:

17 200000
1 194788 3 1 9 6
2 7 18685
1 668957 3 8 12 16
2 5 25666
1 526243 3 13 7 5
2 8 14143
1 49467 3 8 1 17
2 3 25053
1 776279 3 7 11 6
2 5 23689
1 652474 3 4 11 16
2 2 16447
1 104480 3 5 3 14
2 9 23069
1 699675 3 2 15 14
2 3 18743
1 888214 3 17 2 4
2 8 24619
1 626162 3 14 17 3
2 12 20407
1 65049...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1 4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1 7
0
1 38
0
0
0
0
1 20
0
0
1 28
0
0
0
0
0
0
0
1 23
1 21
0
1 40
0
1 32
0
0
0
0
0
0
0
0
0
0
0
2 1 62
0
0
0
0
1 27
1 42
0
3 53 63 81
1 57
0
1 45
1 34
0
0
0
0
0
0
0
1 60
0
0
0
0
1 52
0
2 15 89
0
2 54 94
0
1 70
0
0
1 61
0
0
0
...

result:

ok 100000 lines

Test #9:

score: 0
Accepted
time: 217ms
memory: 75056kb

input:

200000 200000
1 595793 3 1 123431 117674
2 1 5
1 488610 3 1 177503 120691
2 1 5
1 821006 3 1 89129 8171
2 1 3
1 202425 3 1 98222 39855
2 1 1
1 173441 3 1 47510 50873
2 1 1
1 43994 3 1 150434 88334
2 1 3
1 336575 3 1 100731 143443
2 139351 30393
1 867 3 1 155149 2891
2 1 3
1 22448 3 1 193793 152032
2...

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
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 lines

Test #10:

score: 0
Accepted
time: 140ms
memory: 60508kb

input:

200000 200000
1 228748 3 2 98560 10598
2 1 2
1 808541 3 2 34857 97574
2 1 5
1 426853 3 1 76426 192070
2 2 4
1 747544 3 1 105439 24822
2 2 5
1 931575 3 2 162805 154073
2 2 3
1 208881 3 1 185615 2914
2 2 5
1 670938 3 2 60855 116483
2 1 5
1 73426 3 2 24690 9141
2 2 5
1 260124 3 2 97655 111375
2 1 2
1 5...

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
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 lines

Test #11:

score: 0
Accepted
time: 388ms
memory: 122244kb

input:

200000 200000
1 210052 3 1 36549 161634
2 1 10
1 915616 3 3 184683 70284
2 162377 99788
1 772478 3 3 105049 182326
2 1 20
1 379608 3 1 39390 19098
2 99945 52401
1 830086 3 2 174499 190942
2 3 16
1 363236 3 3 115751 9885
2 2 21
1 943439 3 2 80258 46001
2 1 36
1 875219 3 3 143998 53331
2 38341 2315
1 ...

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
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 lines

Test #12:

score: 0
Accepted
time: 746ms
memory: 189464kb

input:

200000 200000
1 2 3 1 143865 120099
1 4 3 1 190911 25916
1 6 3 1 178053 186643
1 8 3 1 141036 104525
1 10 3 1 80225 74496
1 12 3 1 105364 55824
1 14 3 1 115552 32637
1 16 3 1 112278 121633
1 18 3 1 145162 78825
1 20 3 1 20698 115991
1 22 3 1 127458 88470
1 24 3 1 66991 13619
1 26 3 1 124342 175360
1...

output:

1 1
0
1 2
1 3
0
1 4
1 5
0
0
1 6
1 7
1 8
1 9
1 10
0
1 11
0
1 12
0
1 177
1 13
1 14
1 15
1 20357
1 16
1 17
0
1 18
1 19
1 20
1 21
0
1 22
1 23
1 24
0
1 25
1 26
1 27
1 28
0
1 29
0
0
1 30
0
1 31
1 32
1 33
1 34
1 35
1 36
0
1 37
0
0
1 38
1 39
0
0
1 40
0
1 41
0
0
1 42
0
1 43
1 44
0
0
1 45
1 46
1 47
1 48
0
0
1...

result:

ok 100000 lines

Test #13:

score: 0
Accepted
time: 394ms
memory: 113856kb

input:

200000 200000
1 2 3 1 101192 15219
1 4 3 1 57934 110363
1 6 3 1 166877 20608
1 8 3 1 140315 92121
1 10 3 1 154860 172141
1 12 3 2 146060 34724
1 14 3 2 152086 127672
1 16 3 2 121076 179495
1 18 3 1 176976 8288
1 20 3 2 28013 56218
1 22 3 1 58459 127899
1 24 3 1 186216 156690
1 26 3 2 72780 26800
1 2...

output:

0
0
0
0
0
0
0
1 1
0
0
0
1 31707
0
1 2
1 6
0
1 3
0
0
1 7
1 8
1 3479
1 4
0
1 5
1 10
0
0
0
0
0
0
0
0
0
0
0
1 9
0
0
1 11
0
0
1 13
0
0
1 14
1 15
1 12
0
0
0
0
0
1 16
1 17
0
0
0
0
0
0
0
0
0
0
0
1 18
1 19
1 21
1 20
0
0
0
1 22
0
0
0
0
0
0
0
0
1 23
1 24
0
0
1 25
0
1 27
0
1 26
0
1 28
0
0
0
0
0
1 30
1 31
0
1 29...

result:

ok 100000 lines

Test #14:

score: 0
Accepted
time: 263ms
memory: 90068kb

input:

200000 200000
1 2 3 2 55477 107917
1 4 3 3 19358 69971
1 6 3 3 4845 25684
1 8 3 3 87244 180552
1 10 3 1 26548 17274
1 12 3 2 139729 23824
1 14 3 2 188857 68666
1 16 3 3 35589 45253
1 18 3 1 90845 23176
1 20 3 1 168245 46115
1 22 3 3 80442 114240
1 24 3 3 111250 13936
1 26 3 3 174868 145017
1 28 3 3 ...

output:

1 1
0
0
0
0
0
0
0
1 2
0
0
1 3
0
0
1 4
0
0
0
0
0
1 5
0
0
0
0
0
0
0
1 9
0
1 10
0
1 8
0
0
0
0
0
0
0
1 6
1 11
0
1 12
0
0
0
1 13
0
1 7
1 14
0
0
0
0
0
0
1 19
0
0
0
0
0
0
0
0
1 22
0
0
0
0
0
0
0
1 16
0
0
0
1 17
0
0
0
0
1 15
0
0
0
0
0
0
0
1 27
0
1 18
0
1 6695
1 9734
0
0
0
0
0
1 32686
0
0
1 29
0
0
0
0
0
1 20
...

result:

ok 100000 lines

Extra Test:

score: 0
Extra Test Passed