提交记录 3439


用户 题目 状态 得分 用时 内存 语言 代码长度
Centaurus99 noi17a. 【NOI2017】整数 Accepted 100 776.823 ms 46188 KB C++ 3.22 KB
提交时间 评测时间
2018-07-15 12:56:49 2020-07-31 21:17:34
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int ch_top=5e7+3;
char ch[ch_top],*now_r=ch-1,*now_w=ch-1;
inline int read(){
	register int f=1;
	while(*now_r<'0'){
		if (*now_r=='-') f=-1;
		++now_r;
	};
	register int x=*now_r-'0';
	while(*++now_r>='0')x=x*10+*now_r-'0';
	return x*f;
}
const int N=1000010,K=30,MX=(1<<K)-1;
int sum0[N<<2],sum1[N<<2],setv[N<<2],val[N],n;
void create(int o,int l,int r){
	sum0[o]=1,setv[o]=-1;
	if (l==r) return;
	int mid=(l+r)>>1;
	create(o<<1,l,mid);
	create(o<<1|1,mid+1,r);
}
inline void pushup(int o){
	sum0[o]=sum0[o<<1]&sum0[o<<1|1];
	sum1[o]=sum1[o<<1]&sum1[o<<1|1];
}
inline void pushdown(int o,int l,int r){
	if (~setv[o]){
		setv[o<<1]=setv[o<<1|1]=setv[o];
		sum0[o<<1]=sum0[o<<1|1]=setv[o]^1;
		sum1[o<<1]=sum1[o<<1|1]=setv[o]&1;
		int mid=(l+r)>>1;
		if (l==mid) val[l]=setv[o]?MX:0;
		if (mid+1==r) val[r]=setv[o]?MX:0;
		setv[o]=-1;
	}
}
void access(int o,int l,int r,int x){
	if (l==r) return;
	pushdown(o,l,r);
	int mid=(l+r)>>1;
	if (x<=mid) return access(o<<1,l,mid,x);
	else return access(o<<1|1,mid+1,r,x);
}
void qset(int o,int l,int r,int x,int y,int v){
	if (x<=l&&r<=y){
		setv[o]=v;
		sum0[o]=v^1,sum1[o]=v&1;
		if (l==r) val[l]=v?MX:0;
		return;
	}
	pushdown(o,l,r);
	int mid=(l+r)>>1;
	if (y<=mid) qset(o<<1,l,mid,x,y,v);
	else if (x>mid) qset(o<<1|1,mid+1,r,x,y,v);
	else qset(o<<1,l,mid,x,mid,v),qset(o<<1|1,mid+1,r,mid+1,y,v);
	pushup(o);
}
void qchange(int o,int l,int r,int x){
	if (l==r){
		sum0[o]=val[x]==0;
		sum1[o]=val[x]==MX;
		return;
	}
	pushdown(o,l,r);
	int mid=(l+r)>>1;
	if (x<=mid) qchange(o<<1,l,mid,x);
	else qchange(o<<1|1,mid+1,r,x);
	pushup(o);
}
int get0(int o,int l,int r,int x){
	if (sum0[o]) return -1;
	if (l==r) return l+sum0[o];
	pushdown(o,l,r);
	int mid=(l+r)>>1;
	if (x<mid){
		int t=get0(o<<1,l,mid,x);
		return (~t)?t:get0(o<<1|1,mid+1,r,x);
	}
	else return get0(o<<1|1,mid+1,r,x);
}
int get1(int o,int l,int r,int x){
	if (sum1[o]) return -1;
	if (l==r) return l+sum1[o];
	pushdown(o,l,r);
	int mid=(l+r)>>1;
	if (x<mid){
		int t=get1(o<<1,l,mid,x);
		return (~t)?t:get1(o<<1|1,mid+1,r,x);
	}
	else return get1(o<<1|1,mid+1,r,x);
}
void qadd(int x,int v){
	if (!v||x>n) return;
	access(1,1,n,x);
	val[x]+=v;
	int type=val[x]>MX;
	val[x]&=MX;
	qchange(1,1,n,x);
	if (type){
		int to=get1(1,1,n,x);
		if (to<=n){
			access(1,1,n,to);
			++val[to],qchange(1,1,n,to);
			if (to>x+1) qset(1,1,n,x+1,to-1,0);
		}
	}
}
void qminu(int x,int v){
	if (!v||x>n) return;
	access(1,1,n,x);
	val[x]-=v;
	int type=val[x]<0;
	if (type) val[x]+=MX+1;
	qchange(1,1,n,x);
	if (type){
		int to=get0(1,1,n,x);
		if (to<=n){
			access(1,1,n,to);
			--val[to],qchange(1,1,n,to);
			if (to>x+1) qset(1,1,n,x+1,to-1,1);
		}
	}
}
int main(){
	fread(ch,1,ch_top,stdin);
	n=read()+1,read(),read(),read();
	create(1,1,n);
	for (int i=2;i<=n;++i){
		int opt=read();
		if (opt==1){
			int a=read(),b=read();
			int id=b/K+1,id2=b%K;
			unsigned int v=a<0?-a:a;
			v=(v<<id2)&MX;
			if (a>=0) qadd(id,v);
			else qminu(id,v);
			v=a<0?-a:a,v=(v>>(K-id2))&MX;
			if (a>=0) qadd(id+1,v);
			else qminu(id+1,v);
		}
		else{
			int b=read();
			int id=b/K+1,id2=b%K;
			access(1,1,n,id);
			int v=(val[id]>>id2)&1;
			*++now_w=v+'0';
			*++now_w='\n';
		}
	}
	fwrite(ch,1,now_w-ch,stdout);
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #18.16 us36 KBAcceptedScore: 4

Testcase #220.1 us36 KBAcceptedScore: 4

Testcase #3231.18 us96 KBAcceptedScore: 4

Testcase #4359.95 us144 KBAcceptedScore: 4

Testcase #51.911 ms264 KBAcceptedScore: 4

Testcase #61.183 ms252 KBAcceptedScore: 4

Testcase #74.203 ms592 KBAcceptedScore: 4

Testcase #83.285 ms456 KBAcceptedScore: 4

Testcase #915.639 ms1 MB + 384 KBAcceptedScore: 4

Testcase #1030.772 ms2 MB + 564 KBAcceptedScore: 4

Testcase #1128.117 ms1 MB + 976 KBAcceptedScore: 4

Testcase #1217.653 ms2 MB + 496 KBAcceptedScore: 4

Testcase #1341.215 ms4 MB + 444 KBAcceptedScore: 4

Testcase #14130.494 ms10 MB + 84 KBAcceptedScore: 4

Testcase #1598.494 ms16 MB + 664 KBAcceptedScore: 4

Testcase #16284.397 ms20 MB + 380 KBAcceptedScore: 4

Testcase #17293.182 ms15 MB + 992 KBAcceptedScore: 4

Testcase #18446.135 ms36 MB + 636 KBAcceptedScore: 4

Testcase #19525.467 ms38 MB + 756 KBAcceptedScore: 4

Testcase #20249 ms36 MB + 664 KBAcceptedScore: 4

Testcase #21346.395 ms38 MB + 176 KBAcceptedScore: 4

Testcase #22570.845 ms31 MB + 308 KBAcceptedScore: 4

Testcase #23753.629 ms44 MB + 600 KBAcceptedScore: 4

Testcase #24614.759 ms32 MB + 264 KBAcceptedScore: 4

Testcase #25776.823 ms45 MB + 108 KBAcceptedScore: 4


Judge Duck Online | 评测鸭在线
Server Time: 2024-03-28 22:51:53 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用