Submission #956108

#	Time	Username	Problem	Language	Result	Execution time	Memory
956108		batsukh2006	Radio (COCI22_radio)	C++17	30 / 110	399 ms	41128 KiB

Main

#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
• Subtask 2: 30 / 30
• Subtask 3: 0 / 70