oj.uz

Submission #956108

# Submission time Handle Problem Language Result Execution time Memory
956108 2024-04-01T05:35:20 Z batsukh2006 Radio (COCI22_radio) C++17
30 / 110
 399 ms 41128 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int mxN=1e6+1;
vector<int> tree(4*mxN),mp(mxN);
int cal(int node, int L, int R, int l, int r){
    if(L>r||R<l) return 0;
    if(L>=l&&R<=r) return tree[node];
    return max(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]=max(tree[node*2],tree[node*2+1]);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n,q; cin>>n>>q;
	while(q--){
		char c; cin>>c;
		if(c=='S'){
			int x; cin>>x;
			int sv=x;
			int cnt=0;
			while(x%2==0){
				cnt++;
				x/=2;
			}
			if(cnt>0){
				if(mp[sv]) up(1,1,n,2,-1);
				else up(1,1,n,2,1);
			}
			for(int i=3; i<=sqrt(x); i+=2){ 
				cnt=0;
		        while(x%i==0){ 
		        	cnt++;
		            x=x/i; 
		        }
		        if(cnt>0){
					if(mp[sv]) up(1,1,n,i,-1);
					else up(1,1,n,i,1);
				}
	    	}
	    	if(x>2){
	    		if(mp[sv]) up(1,1,n,x,-1);
				else up(1,1,n,x,1);
			}
			mp[sv]^=1; 
		}else{ 
			int l,r; cin>>l>>r;
			if(cal(1,1,n,l,r)>1) cout<<"DA"<<endl;
			else cout<<"NE"<<endl;
		}
	}
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 39780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 40544 KB Output is correct
2 Correct 138 ms 41040 KB Output is correct
3 Correct 178 ms 41128 KB Output is correct
4 Correct 24 ms 39768 KB Output is correct
5 Correct 153 ms 40208 KB Output is correct
6 Correct 399 ms 40852 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 39780 KB Output isn't correct
2 Halted 0 ms 0 KB -