oj.uz

Submission #868554

# Submission time Handle Problem Language Result Execution time Memory
868554 2023-10-31T20:02:36 Z epicci23 Radio (COCI22_radio) C++17
40 / 110
 1271 ms 299892 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];
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+1,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());
            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);
              seg.upd(1,1,n,(*it),*ll[(*it)].rbegin());
            }
            ll[u].clear();
            ll[u].insert(0);
            seg.upd(1,1,n,u,0);
    		  }
      	}
     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 367 ms 164640 KB Output is correct
2 Correct 354 ms 164364 KB Output is correct
3 Correct 352 ms 164520 KB Output is correct
4 Correct 343 ms 164320 KB Output is correct
5 Correct 355 ms 164568 KB Output is correct
6 Correct 345 ms 164532 KB Output is correct
7 Correct 389 ms 164404 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 852 ms 187556 KB Output is correct
2 Correct 1183 ms 247600 KB Output is correct
3 Correct 1271 ms 299892 KB Output is correct
4 Correct 369 ms 173380 KB Output is correct
5 Correct 443 ms 208252 KB Output is correct
6 Correct 504 ms 252040 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 164640 KB Output is correct
2 Correct 354 ms 164364 KB Output is correct
3 Correct 352 ms 164520 KB Output is correct
4 Correct 343 ms 164320 KB Output is correct
5 Correct 355 ms 164568 KB Output is correct
6 Correct 345 ms 164532 KB Output is correct
7 Correct 389 ms 164404 KB Output is correct
8 Correct 852 ms 187556 KB Output is correct
9 Correct 1183 ms 247600 KB Output is correct
10 Correct 1271 ms 299892 KB Output is correct
11 Correct 369 ms 173380 KB Output is correct
12 Correct 443 ms 208252 KB Output is correct
13 Correct 504 ms 252040 KB Output is correct
14 Incorrect 554 ms 166336 KB Output isn't correct
15 Halted 0 ms 0 KB -