Submission #868556

#	Time	Username	Problem	Language	Result	Execution time	Memory
868556		epicci23	Radio (COCI22_radio)	C++17	40 / 110	1145 ms	264888 KiB

Main

#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
//#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define m (l+r)/2

const int N = 1e6 + 5;

struct segT{
  vector<int> seg;
  int n;
  segT(int x){
  	this->n=x;
  	seg.resize(4*x+5);
  }

  inline void upd(int rt,int l,int r,int x,int u){
  	 if(r<x || l>x) return;
  	 if(l==r){
  	   seg[rt]=u;
  	   return;
  	 }
  	 upd(rt*2,l,m,x,u);
  	 upd(rt*2+1,m+1,r,x,u);
  	 seg[rt]=max(seg[rt*2],seg[rt*2+1]);
  }

  inline int query(int rt,int l,int r,int gl,int gr){
  	if(l>=gl && r<=gr) return seg[rt];
  	if(r<gl || l>gr) return 0;
  	return max(query(rt*2,l,m,gl,gr),query(rt*2+1,m+1,r,gl,gr));
  }
};


vector<int> primes[N];
set<int> s[N];
set<int> ll[N];

void solve(){

  for(int i=2;i<N;i++){
    if(!primes[i].empty()) continue;
    for(int j=i;j<N;j+=i) primes[j].pb(i);
  }

  int n,q;
  cin >> n >> q;
  for(int i=0;i<N;i++) ll[i].insert(0);
  segT seg(N);
  vector<int> act(N,0);
  while(q--){
  	char xd;
  	cin >> xd;
  	if(xd=='S'){
  		int u;
  		cin >> u;
  		if(!act[u]){
    		  for(int x:primes[u]){
    		  	auto it = s[x].lower_bound(u);
    		  	if(it!=s[x].begin()){
    		  	  it--;
    		  	  ll[u].insert(*it);
    		  	}
            seg.upd(1,1,n,u,*ll[u].rbegin());
            assert(*ll[u].rbegin() < u);
            it = s[x].lower_bound(u);
            if(it!=s[x].end()){
              ll[*it].insert(u);
              seg.upd(1,1,n,(*it),*ll[(*it)].rbegin());
            }
            s[x].insert(u);
    		  }  
  	    }
  	    else{
          for(int x:primes[u]){
            s[x].erase(u); 
    		  	auto it = s[x].lower_bound(u);
            if(it!=s[x].end()){
              ll[*it].erase(u);
              if(it!=s[x].begin()){
                auto hmhm = it;
                hmhm--;
                ll[*it].insert(*hmhm);
              }
              seg.upd(1,1,n,(*it),*ll[(*it)].rbegin());
              assert(*ll[u].rbegin() < u);
            }
            ll[u].clear();
            ll[u].insert(0);
            seg.upd(1,1,n,u,0);
            assert(*ll[u].rbegin() < u);
    		  }
      	}
     act[u]^=1;
  	}  
  	else{
  	  int a,b;
  	  cin >> a >> b;
  	  int lol = seg.query(1,1,n,a,b);
      if(lol>=a) cout << "DA\n";
      else cout << "NE\n";
  	}
  }
}

int32_t main(){

  cin.tie(0); ios::sync_with_stdio(0);
  
  int t=1;//cin >> t;
  while(t--) solve();

  return 0;
}

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