oj.uz

Submission #868555

# Submission time Handle Problem Language Result Execution time Memory
868555 2023-10-31T20:14:08 Z epicci23 Radio (COCI22_radio) C++17
40 / 110
 1500 ms 340740 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


const int N = 1e6 + 5;

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

  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]);
  }

  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 404 ms 274004 KB Output is correct
2 Correct 458 ms 274192 KB Output is correct
3 Correct 399 ms 274004 KB Output is correct
4 Correct 413 ms 274256 KB Output is correct
5 Correct 413 ms 274080 KB Output is correct
6 Correct 410 ms 274112 KB Output is correct
7 Correct 410 ms 274000 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 964 ms 292780 KB Output is correct
2 Correct 1377 ms 320940 KB Output is correct
3 Correct 1443 ms 330724 KB Output is correct
4 Correct 417 ms 274100 KB Output is correct
5 Correct 456 ms 274068 KB Output is correct
6 Correct 548 ms 274004 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 274004 KB Output is correct
2 Correct 458 ms 274192 KB Output is correct
3 Correct 399 ms 274004 KB Output is correct
4 Correct 413 ms 274256 KB Output is correct
5 Correct 413 ms 274080 KB Output is correct
6 Correct 410 ms 274112 KB Output is correct
7 Correct 410 ms 274000 KB Output is correct
8 Correct 964 ms 292780 KB Output is correct
9 Correct 1377 ms 320940 KB Output is correct
10 Correct 1443 ms 330724 KB Output is correct
11 Correct 417 ms 274100 KB Output is correct
12 Correct 456 ms 274068 KB Output is correct
13 Correct 548 ms 274004 KB Output is correct
14 Correct 668 ms 274920 KB Output is correct
15 Correct 1160 ms 288456 KB Output is correct
16 Execution timed out 1591 ms 340740 KB Time limit exceeded
17 Halted 0 ms 0 KB -