QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#425513 | #8302. Incoming Asteroids | DaiRuiChen007 | TL | 3ms | 14532kb | C++14 | 1.1kb | 2024-05-30 12:21:15 | 2024-05-30 12:21:15 |
Judging History
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 ...