QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#371606#8302. Incoming Asteroidsucup-team052#WA 140ms37052kbC++232.1kb2024-03-30 14:22:512024-03-30 14:24:26

Judging History

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

  • [2024-03-30 14:24:26]
  • 评测
  • 测评结果:WA
  • 用时:140ms
  • 内存:37052kb
  • [2024-03-30 14:22:51]
  • 提交

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)
using namespace std;
using LL=long long;
const int inf=0x3f3f3f3f;
#define int long long
#define N 200005
const int MAGIC=1000;
int read()
{
	int x; scanf("%lld",&x);
	return x;
}
int n,Q,m;
int sz[N],q[N][3],lst[N][3],start[N][3],sum[N],ned[N],ok[N];
vector<int> presum[N],all[N],ready[N];
int lstpos[N];
void wait(int id)
{
	for(int i=0;i<sz[id];i++) all[q[id][i]].push_back(id);
	if(ned[id]<=sz[id]*MAGIC)
	{
		for(int i=0;i<sz[id];i++) ready[q[id][i]].push_back(id);
	}
}
int getsiz(int id)
{
	int sum=0;
	for(int i=0;i<sz[id];i++)
	{
		int u=q[id][i],st=start[id][i];
		sum+=presum[u].back()-presum[u][st];
	}
	return sum;
}
vector<int> ans;
signed main(){
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	cin>>n>>Q;
	int _lst=0;
	for(int i=1;i<=n;i++) presum[i].push_back(0);
	while(Q--)
	{
		int op=read();
		if(op==1)
		{
			m++;
			ned[m]=read()^_lst,sz[m]=read();
			for(int i=0;i<sz[m];i++)
			{
				q[m][i]=read()^_lst;
				start[m][i]=presum[q[m][i]].size()-1;
			}
			wait(m);
		}
		else
		{
			int x=read()^_lst,y=read()^_lst;
			presum[x].push_back(presum[x].back()+y);
			ans.clear();
			if(presum[x].back()-presum[x][lstpos[x]]<MAGIC)
			{
				vector<int> nw;
				for(int j:ready[x])
				{
					if(ok[j]==1) continue;
					if(getsiz(j)>=ned[j]) ans.push_back(j),ok[j]=1;
					else nw.push_back(j);
				}
				swap(ready[x],nw);
			}
			else
			{
				vector<int> nw;
				for(int j:all[x])
				{
					if(ok[j]==1) continue;
					int siz=getsiz(j);
					if(siz>=ned[j]) ans.push_back(j),ok[j]=1;
					else
					{
						nw.push_back(j);
						if(ok[j]!=2&&ned[j]-siz<=sz[j]*MAGIC)
						{
							ok[j]=2;
							for(int i=0;i<sz[j];i++) ready[q[j][i]].push_back(j);
						}
					}
				}
				swap(all[x],nw);
				lstpos[x]=presum[x].size()-1;
			}
			_lst=ans.size();
			if(_lst==0) printf("0\n");
			else
			{
				printf("%lld ",_lst);
				for(int i=0;i<_lst;i++) printf("%lld%c",ans[i]," \n"[i==_lst-1]);
			}
		}
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3804kb

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: 113ms
memory: 36092kb

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: 125ms
memory: 37052kb

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: 134ms
memory: 35524kb

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: 123ms
memory: 18100kb

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: 140ms
memory: 14700kb

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: -100
Wrong Answer
time: 101ms
memory: 11932kb

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:

wrong answer 89097th lines differ - expected: '2 85906 88530', found: '2 88530 85906'