제출 #868558

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
868558		epicci23	Radio (COCI22_radio)	C++17	110 / 110	1499 ms	301168 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
#pragma GCC optimize("O3")
 
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];
vector<int> zort[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);
              zort[*it].pb(u);
            }
            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);
              zort[u].pb(*it);
              seg.upd(1,1,n,(*it),*ll[(*it)].rbegin());
            }
            s[x].insert(u);
          }  
        }
        else{
          for(int x:zort[u]){ 
            ll[x].erase(u);
            seg.upd(1,1,n,x,*ll[x].rbegin());
          }
          zort[u].clear();
          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);
                zort[*hmhm].pb(*it);
              }
              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: 70 / 70