QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#882233#8302. Incoming Asteroidssz051ML 0ms0kbC++202.4kb2025-02-04 22:31:112025-02-04 22:31:12

Judging History

This is the latest submission verdict.

  • [2025-02-04 22:31:12]
  • Judged
  • Verdict: ML
  • Time: 0ms
  • Memory: 0kb
  • [2025-02-04 22:31:11]
  • 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;
struct Alarm{
	int qlim[1000010],qh[1000010],delt[1000010],qcnt=0;
	Array qp[1000010];
	Array seps[1000010][22];
	int sum[1000010];
	Alarm(){}
	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;
	}
} alarm;
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("%lld ",cur.size());
			for(int i:cur){
				printf("%lld ",i);
			}
			putchar('\n');
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Memory Limit Exceeded

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: