oj.uz

Submission #957196

# Submission time Handle Problem Language Result Execution time Memory
957196 2024-04-03T07:04:48 Z vjudge1 Radio (COCI22_radio) C++17
110 / 110
 1413 ms 200368 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 112472 KB Output is correct
2 Correct 22 ms 112476 KB Output is correct
3 Correct 22 ms 112592 KB Output is correct
4 Correct 23 ms 112688 KB Output is correct
5 Correct 25 ms 112680 KB Output is correct
6 Correct 23 ms 112472 KB Output is correct
7 Correct 22 ms 112476 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 127972 KB Output is correct
2 Correct 902 ms 165204 KB Output is correct
3 Correct 1156 ms 195016 KB Output is correct
4 Correct 32 ms 115804 KB Output is correct
5 Correct 88 ms 135256 KB Output is correct
6 Correct 157 ms 159348 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 112472 KB Output is correct
2 Correct 22 ms 112476 KB Output is correct
3 Correct 22 ms 112592 KB Output is correct
4 Correct 23 ms 112688 KB Output is correct
5 Correct 25 ms 112680 KB Output is correct
6 Correct 23 ms 112472 KB Output is correct
7 Correct 22 ms 112476 KB Output is correct
8 Correct 462 ms 127972 KB Output is correct
9 Correct 902 ms 165204 KB Output is correct
10 Correct 1156 ms 195016 KB Output is correct
11 Correct 32 ms 115804 KB Output is correct
12 Correct 88 ms 135256 KB Output is correct
13 Correct 157 ms 159348 KB Output is correct
14 Correct 237 ms 114260 KB Output is correct
15 Correct 607 ms 121456 KB Output is correct
16 Correct 1413 ms 200368 KB Output is correct
17 Correct 1034 ms 192772 KB Output is correct
18 Correct 1189 ms 197052 KB Output is correct
19 Correct 1175 ms 196812 KB Output is correct
20 Correct 162 ms 159408 KB Output is correct
21 Correct 183 ms 159444 KB Output is correct
22 Correct 171 ms 159572 KB Output is correct
23 Correct 172 ms 159452 KB Output is correct