QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#882287#8302. Incoming Asteroidssz051WA 105ms122580kbC++202.2kb2025-02-04 23:18:472025-02-04 23:18:47

Judging History

This is the latest submission verdict.

  • [2025-02-04 23:18:47]
  • Judged
  • Verdict: WA
  • Time: 105ms
  • Memory: 122580kb
  • [2025-02-04 23:18:47]
  • Submitted

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;
	vector<int> qp[200010];
	vector<int> seps[200010][22];
	int sum[200010];
	int insert(vector<int> pos,int lim){
		//<P7603 only>
		//</>
		qlim[++qcnt]=lim;
		qp[qcnt]=pos;
		qh[qcnt]=20;
		while(qh[qcnt]>=0){
			int cur=0;
			for(int i:pos){
				cur+=sum[i]|((1ll<<qh[qcnt])-1);
			}
			if(cur>=lim){
				qh[qcnt]--;
			}else{
				break;
			}
		}
		for(int i:pos){
			seps[i][qh[qcnt]+1].push_back(qcnt);
		}
		return qcnt;
	}
	vector<int> update(int k,int v){
		vector<int> res;
		int tp=lg(sum[k]^(sum[k]+v));
		sum[k]+=v;
		for(int p=-1;p<=tp;p++){
			vector<int> 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;
				}
				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{
						break;
					}
				}
				if(qh[i]==-1){
					res.push_back(i);	
				}else{
					if(qh[i]==p){
						seps[k][p+1].push_back(i);
					}else{
						for(int j:qp[i]){
							seps[j][qh[i]+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: 4ms
memory: 5840kb

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: 105ms
memory: 122580kb

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'