oj.uz

Submission #971659

# Submission time Handle Problem Language Result Execution time Memory
971659 2024-04-29T06:54:44 Z batsukh2006 Radio (COCI22_radio) C++17
110 / 110
 985 ms 116556 KB 
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<map>
#include<string>
#include<algorithm>
#include<vector>
#include<string.h>
#include<utility>
#include<set>
#include<cmath>
#include<queue>
#include<deque>
#include<functional>
#include<stack>
#include<limits.h>
#include<iomanip>
#include<unordered_map> 
#include<numeric>
#include<tuple>
using namespace std;
 
#define MOD 1000000007
#define int long long
#define endl '\n'
const int mxN=1e6+1;
vector<bool> ok(mxN);
vector<int> tree(4*mxN,1e9),pf(mxN),mp(mxN);
int cal(int node, int L, int R, int l, int r){
    if(L>r||R<l) return 1e9;
    if(L>=l&&R<=r) return tree[node];
    return min(cal(node*2,L,(L+R)/2,l,r),cal(node*2+1,(L+R)/2+1,R,l,r));
}
void up(int node, int L, int R, int p, int v){
    if(L>p||R<p) return;
    if(L==R){
        tree[node]=v;
        return;
    }
    up(node*2,L,(L+R)/2,p,v);
    up(node*2+1,(L+R)/2+1,R,p,v);
    tree[node]=min(tree[node*2],tree[node*2+1]);
}
void solve(){
	int n,q; cin>>n>>q;
	set<int> s[n+1];
	for(int i=1; i<=n; i++) pf[i]=i;
	for(int i=2; i*i<=n; i++){
		if(!ok[i]){
			for(int k=i*i; k<=n; k+=i){
				if(!ok[k]) pf[k]=i;
				ok[k]=1;
			}
		}
	}
	while(q--){
		char c; cin>>c;
		if(c=='S'){
			int x; cin>>x;
			int real=x;
			if(!mp[real]){
				int c=cal(1,1,n,x,x);
				while(pf[x]>1){
					if(s[pf[x]].find(real)==s[pf[x]].end()){
						s[pf[x]].insert(real);
						auto it=s[pf[x]].find(real);
						int sp=1e9;
						if(it!=prev(s[pf[x]].end())) c=min(c,*next(it));
						if(it!=s[pf[x]].begin()) sp=cal(1,1,n,*prev(it),*prev(it));
						if(it!=s[pf[x]].begin()) up(1,1,n,*prev(it),min(sp,real));
						x/=pf[x];
					}else{
						x/=pf[x];
					}
				}
				up(1,1,n,real,c);
			}else{
				up(1,1,n,x,1e9);
				while(pf[x]>1){
					auto it=s[pf[x]].find(real);
					if(it!=s[pf[x]].end()){
						if(it!=s[pf[x]].begin()){
							int z=*prev(it);
							int real1=z;
							int c=1e9;
							while(pf[z]>1){
								if(pf[z]!=pf[x]){
									auto itr=s[pf[z]].find(real1);
									if(itr!=prev(s[pf[z]].end())) c=min(c,*next(itr));
								}
								z/=pf[z];
							}
							if(it!=prev(s[pf[x]].end())) up(1,1,n,real1,min(c,*next(it)));
							else up(1,1,n,real1,c);
						}
						s[pf[x]].erase(real);
						x/=pf[x];
					}else{
						x/=pf[x];
					}
				}
			}
			mp[real]^=1;
		}else{
			int l,r; cin>>l>>r;
			if(cal(1,1,n,l,r)<=r) cout<<"DA"<<endl;
			else cout<<"NE"<<endl;
		}
	}
}
signed main(){
    // freopen("248.in", "r", stdin);
    // freopen("248.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t=1;
//    cin>>t;	
    while(t--){
        solve();
        cout<<endl;
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47452 KB Output is correct
2 Correct 13 ms 47460 KB Output is correct
3 Correct 11 ms 47452 KB Output is correct
4 Correct 11 ms 47452 KB Output is correct
5 Correct 10 ms 47452 KB Output is correct
6 Correct 10 ms 47564 KB Output is correct
7 Correct 10 ms 47448 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 57684 KB Output is correct
2 Correct 652 ms 85608 KB Output is correct
3 Correct 794 ms 112156 KB Output is correct
4 Correct 21 ms 52060 KB Output is correct
5 Correct 78 ms 70924 KB Output is correct
6 Correct 183 ms 94316 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47452 KB Output is correct
2 Correct 13 ms 47460 KB Output is correct
3 Correct 11 ms 47452 KB Output is correct
4 Correct 11 ms 47452 KB Output is correct
5 Correct 10 ms 47452 KB Output is correct
6 Correct 10 ms 47564 KB Output is correct
7 Correct 10 ms 47448 KB Output is correct
8 Correct 325 ms 57684 KB Output is correct
9 Correct 652 ms 85608 KB Output is correct
10 Correct 794 ms 112156 KB Output is correct
11 Correct 21 ms 52060 KB Output is correct
12 Correct 78 ms 70924 KB Output is correct
13 Correct 183 ms 94316 KB Output is correct
14 Correct 215 ms 48920 KB Output is correct
15 Correct 453 ms 54732 KB Output is correct
16 Correct 985 ms 116556 KB Output is correct
17 Correct 767 ms 113240 KB Output is correct
18 Correct 873 ms 115028 KB Output is correct
19 Correct 910 ms 114976 KB Output is correct
20 Correct 160 ms 95828 KB Output is correct
21 Correct 168 ms 96252 KB Output is correct
22 Correct 162 ms 95828 KB Output is correct
23 Correct 161 ms 95820 KB Output is correct