QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#425513#8302. Incoming AsteroidsDaiRuiChen007TL 3ms14532kbC++141.1kb2024-05-30 12:21:152024-05-30 12:21:15

Judging History

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

  • [2024-05-30 12:21:15]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:14532kb
  • [2024-05-30 12:21:15]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
ll lim[MAXN],up[MAXN],sum[MAXN];
vector <int> pos[MAXN];
priority_queue <array<ll,2>,vector<array<ll,2>>,greater<array<ll,2>>> f[MAXN];
signed main() {
	int n,m=0,q,lst=0;
	ios::sync_with_stdio(false);
	cin>>n>>q;
	while(q--) {
		int op;
		cin>>op;
		if(op==1) {
			int k,c;
			cin>>k>>c,k^=lst,lim[++m]=k,pos[m].resize(c),up[m]=(k+c-1)/c;
			for(int &i:pos[m]) cin>>i,i^=lst,lim[m]+=sum[i],f[i].push({up[m],m});
		} else {
			int u,w;
			cin>>u>>w,u^=lst,w^=lst,sum[u]+=w;
			vector <int> ans;
			while(f[u].size()) {
				while(f[u].size()&&f[u].top()[0]!=up[f[u].top()[1]]) f[u].pop();
				if(f[u].empty()||f[u].top()[0]>sum[u]) break;
				int i=f[u].top()[1]; f[u].pop();
				ll rem=lim[i];
				for(int j:pos[i]) rem-=sum[j];
				if(rem<=0) ans.push_back(i),up[i]=-1;
				else {
					up[i]=(rem-1)/pos[i].size()+1;
					for(int j:pos[i]) f[j].push({up[i],i});
				}
			}
			sort(ans.begin(),ans.end()),cout<<(lst=ans.size());
			for(int x:ans) cout<<" "<<x; cout<<"\n";
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 14532kb

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: -100
Time Limit Exceeded

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: