QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#882240#8302. Incoming Asteroidssz051WA 103ms123604kbC++202.4kb2025-02-04 22:34:452025-02-04 22:34:46

Judging History

This is the latest submission verdict.

  • [2025-02-04 22:34:46]
  • Judged
  • Verdict: WA
  • Time: 103ms
  • Memory: 123604kb
  • [2025-02-04 22:34:45]
  • Submitted

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%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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 18ms
memory: 8020kb

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: 103ms
memory: 123604kb

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 7787th lines differ - expected: '0', found: '1 3640'