QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#882271 | #8302. Incoming Asteroids | sz051 | WA | 119ms | 218800kb | C++20 | 2.4kb | 2025-02-04 22:58:03 | 2025-02-04 22:58:03 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cassert>
#include <stack>
#include <random>
#include <map>
#define int long long
using namespace std;
void read(int &x){
x=0;
int f=1;
char c=getchar();
while(!('0'<=c && c<='9')){
if(c=='-'){
f=-1;
}
c=getchar();
}
while('0'<=c && c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
x*=f;
}
int lg(int k){
return k==0?-1:__lg(k);
}
typedef vector<int> Array;
namespace Alarm{
int qlim[200010],qh[200010],delt[200010],qcnt=0;
Array qp[200010];
Array seps[200010][43];
int sum[200010];
int insert(Array pos,int lim){
for(int i:pos){
lim+=sum[i];
}
qlim[++qcnt]=lim;
qp[qcnt]=pos;
qh[qcnt]=41;
while(qh[qcnt]>=0){
int cur=0;
for(int i:pos){
cur+=sum[i]|((1ll<<qh[qcnt])-1);
}
if(cur>=lim){
qh[qcnt]--;
}else{
delt[qcnt]=cur;
break;
}
}
for(int i:pos){
seps[i][qh[qcnt]+1].push_back(qcnt);
}
return qcnt;
}
Array update(int k,int v){
Array res;
int tp=lg(sum[k]^(sum[k]+v));
sum[k]+=v;
for(int p=-1;p<=tp;p++){
Array tmp=seps[k][p+1];
seps[k][p+1].clear();
for(int i:tmp){
if(qh[i]!=p){
continue;
}
if(delt[i]-((sum[k]-v)|((1ll<<p)-1))+(sum[k]|((1ll<<p)-1))>=qlim[i]){
qh[i]--;
while(qh[i]>=0){
int cur=0;
for(int j:qp[i]){
cur+=sum[j]|((1ll<<qh[i])-1);
}
if(cur>=qlim[i]){
qh[i]--;
}else{
delt[i]=cur;
break;
}
}
if(qh[i]==-1){
res.push_back(i);
}else{
for(int j:qp[i]){
seps[j][qh[i]+1].push_back(i);
}
}
}else{
if(qh[i]==-1){
res.push_back(i);
}else{
delt[i]+=-((sum[k]-v)|((1ll<<p)-1))+(sum[k]|((1ll<<p)-1));
seps[k][p+1].push_back(i);
}
}
}
}
return res;
}
}
int n,m;
signed main(){
read(n);
read(m);
int opt,x,y;
while(m--){
read(opt);
if(opt==1){
read(x);
read(y);
Array cur(y,0);
for(int i=0;i<y;i++){
read(cur[i]);
}
Alarm::insert(cur,x);
}else{
read(x);
read(y);
Array cur=Alarm::update(x,y);
sort(cur.begin(),cur.end());
printf("%d%c",cur.size(),cur.size()?' ':'\n');
for(int i=0;i<cur.size();i++){
printf("%d%c",cur[i],i==cur.size()-1?'\n':' ');
}
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 6ms
memory: 5968kb
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
Wrong Answer
time: 119ms
memory: 218800kb
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:
wrong answer 9592nd lines differ - expected: '0', found: '1 2589'