oj.uz

Submission #868558

# Submission time Handle Problem Language Result Execution time Memory
868558 2023-10-31T20:18:17 Z epicci23 Radio (COCI22_radio) C++17
110 / 110
 1499 ms 301168 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 239700 KB Output is correct
2 Correct 324 ms 239696 KB Output is correct
3 Correct 326 ms 239696 KB Output is correct
4 Correct 325 ms 239956 KB Output is correct
5 Correct 320 ms 239844 KB Output is correct
6 Correct 324 ms 239696 KB Output is correct
7 Correct 347 ms 239828 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 871 ms 256924 KB Output is correct
2 Correct 1213 ms 283860 KB Output is correct
3 Correct 1300 ms 293712 KB Output is correct
4 Correct 332 ms 239700 KB Output is correct
5 Correct 385 ms 239696 KB Output is correct
6 Correct 428 ms 239828 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 239700 KB Output is correct
2 Correct 324 ms 239696 KB Output is correct
3 Correct 326 ms 239696 KB Output is correct
4 Correct 325 ms 239956 KB Output is correct
5 Correct 320 ms 239844 KB Output is correct
6 Correct 324 ms 239696 KB Output is correct
7 Correct 347 ms 239828 KB Output is correct
8 Correct 871 ms 256924 KB Output is correct
9 Correct 1213 ms 283860 KB Output is correct
10 Correct 1300 ms 293712 KB Output is correct
11 Correct 332 ms 239700 KB Output is correct
12 Correct 385 ms 239696 KB Output is correct
13 Correct 428 ms 239828 KB Output is correct
14 Correct 605 ms 240404 KB Output is correct
15 Correct 900 ms 250336 KB Output is correct
16 Correct 1499 ms 301168 KB Output is correct
17 Correct 1265 ms 291468 KB Output is correct
18 Correct 1396 ms 297300 KB Output is correct
19 Correct 1343 ms 297128 KB Output is correct
20 Correct 426 ms 241316 KB Output is correct
21 Correct 436 ms 241652 KB Output is correct
22 Correct 436 ms 241236 KB Output is correct
23 Correct 430 ms 241520 KB Output is correct