제출 #957196

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
957196		vjudge1	Radio (COCI22_radio)	C++17	110 / 110	1413 ms	200368 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define LL int
LL n,i,j,k,m,l,r,x,useless;
LL tree[4000005];
LL a[1000005][12];
set<LL> st[1000005];
set<LL,greater<LL> > st1[1000005];
char ch;
bool flag[1000005];
const LL inf=0x7fffffff;
void insert(LL l,LL r,LL id,LL x,LL val){
	if(l==r && r==x){
		tree[id]=val;
		return ;
	}
	LL mid=(l+r)>>1;
	if(x<=mid) insert(l,mid,id*2,x,val);
	else insert(mid+1,r,id*2+1,x,val);
	tree[id]=min(tree[id*2],tree[id*2+1]);
}
LL query(LL l,LL r,LL id,LL askl,LL askr){
	if(l>=askl && r<=askr){
		return tree[id];
	}
	LL mid=(l+r)>>1,minx=inf;
	if(askl<=mid) minx=min(minx,query(l,mid,id*2,askl,askr));
	if(askr>mid) minx=min(minx,query(mid+1,r,id*2+1,askl,askr));
	return minx;
}
void update(LL x){
	LL num=inf;
	for(LL i=1;i<=a[x][0];i++){
		auto tmp=st[a[x][i]].upper_bound(x);
		if(tmp!=st[a[x][i]].end()) num=min(num,*tmp);
	}
	//printf("%lld %lld\n",x,num);
	insert(1,n,1,x,num);
}
LL read(){
	useless=0;
	while(ch<'0' || ch>'9') ch=getchar();
	while(ch>='0' && ch<='9'){
		useless=useless*10+ch-'0';
		ch=getchar();
	}
	return useless;
}
int main(){
	ios::sync_with_stdio(false);
	memset(tree,0x7f,sizeof(tree));
	cin>>n>>m;
	for(i=2;i<=n;i++){
		if(a[i][0]==0){
			for(j=1;i*j<=n;j++){
				a[i*j][0]++;
				a[i*j][a[i*j][0]]=i;
			}
		}
	}
	for(i=1;i<=m;i++){
	    cin>>ch;
		if(ch=='S'){
			cin>>x;
			if(flag[x]==false){
				flag[x]=true;
				update(x);
				for(j=1;j<=a[x][0];j++){
					st[a[x][j]].insert(x);
					st1[a[x][j]].insert(x);
				}
				for(j=1;j<=a[x][0];j++){
					auto tmp=st1[a[x][j]].upper_bound(x);
					if(tmp!=st1[a[x][j]].end()) update(*tmp);
				}
			}
			else{
				flag[x]=false;
				insert(1,n,1,x,inf);
				for(j=1;j<=a[x][0];j++){
					st[a[x][j]].erase(x);
					st1[a[x][j]].erase(x);
				}	
				for(j=1;j<=a[x][0];j++){
					auto tmp=st1[a[x][j]].upper_bound(x);
					if(tmp!=st1[a[x][j]].end()) update(*tmp);
				}
			}
		}
		else{
			cin>>l>>r;
			if(query(1,n,1,l,r)<=r) printf("DA\n");
			else printf("NE\n");
		}
	} 
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70