QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#882238 | #8302. Incoming Asteroids | sz051 | WA | 21ms | 7892kb | C++20 | 2.3kb | 2025-02-04 22:33:18 | 2025-02-04 22:33:20 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cassert>
#include <stack>
#include <random>
#include <map>
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[1000010],qh[1000010],delt[1000010],qcnt=0;
Array qp[1000010];
Array seps[1000010][22];
int sum[1000010];
int insert(Array pos,int lim){
qlim[++qcnt]=lim;
qp[qcnt]=pos;
qh[qcnt]=21;
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){
//printf("[%lld %lld %lld]",k,p,i);
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 ",cur.size());
for(int i:cur){
printf("%d ",i);
}
putchar('\n');
}
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 21ms
memory: 7892kb
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:
wrong answer 1st lines differ - expected: '0', found: '0 '