Submission #795248

#	Time	Username	Problem	Language	Result	Execution time	Memory
795248		makanhulia	Radio (COCI22_radio)	C++17	10 / 110	1584 ms	2080 KiB

Main

#include <bits/stdc++.h>
namespace bijiEnak {
  using namespace std;
  using ll = long long;
  // #define int long long // on or off
  #define vi vector<int>
  #define vi2D vector<vi>
  #define pii pair<int, int>
  #define fr first
  #define sc second
  #define mpr make_pair
  #define umap unordered_map
  #define biji ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);    
  //lower_bound(x) : >= x
  //upper_bound(x) : > x
  const int MOD = 1e9 + 7;
  const int MAXN = 2e5 + 1;
  const string input = {'_', 'i', 'n', 'p', 'u', 't', '.', 't', 'x', 't'};
  const string output = {'_', 'o', 'u', 't', 'p', 'u', 't', '.', 't', 'x', 't'};
  const string input_r = {'r'};
  const string output_w = {'w'};
}
using namespace bijiEnak;
  
vector<int> primes;
void sieve(int n) {
  vector<bool> done(n);
  primes.resize(n);
  for(int i = 1; i <= n; i++) primes[i] = i;
  for(int i = 2; i*i < n; i++) {
    if(done[i]) continue;
    for(int j = i*i; j < n; j += i) {
      done[j] = true;
      primes[j] = min(i, primes[j]);
    }
  }
}
bool check(int x, map<int,bool>& mp) {
  while(x > 1) {
    int p = primes[x];
    if(mp.count(p)) return false;
    mp[p] = true;
    while(x != 1 && x % p == 0) x /= p;
  }
  return true;
}

set<int> st;
void S() {
  int x; cin >> x;
  if(st.count(x)) st.erase(x);
  else st.insert(x);
}
void C() {
  int l, r; cin >> l >> r;
  map<int, bool> mp;
  bool sw = true;
  auto a = st.lower_bound(l), b = st.upper_bound(r);
  for(; a != b; ++a) if(!check(*a, mp)) sw = false;

  if(sw) cout << "NE\n";
  else cout << "DA\n";
}
void tcsolve() {
  int N, Q; cin >> N >> Q;
  sieve(N+1);

  while(Q--) {
    char cm; cin >> cm;
    if(cm == 'S') S();
    else C();
  }

}
  
signed main() {
  // freopen(input.c_str(), input_r.c_str(), stdin);
  // freopen(output.c_str(), output_w.c_str(), stdout);
  
  biji int t = 1;
  // cin >> t;
  while(t--) tcsolve();
  
  return 0;
}
/*                                                           DOGE
                ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣤⠤⠤⠴⠒⠒⠒⠶⠶⠶⠤⠤⠴⠶⠶⠤⠤⠤⠤⠤⠤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
                ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⠟⠉⢀⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⢀  ⣈⠱⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
                ⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⠟⢁⣠⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀  ⠙⣷⡈⠛⢦⣄⠀⠀⠀⠀⠀⠀⠀⠀
                ⠀⠀⠀⠀⠀⠀⠀⢀⡴⠻⠋⣺⣽⡿⠀⠀⠀⠀⣀⡀⠀⠀⠆⠀⠀⠀⠀⠀⠀⢠⣴⣦⣀⠀⠀⠀ ⠘⣿⣦⡀⠙⢷⣄⠀⠀⠀⠀⠀⠀
                ⠀⠀⠀⠀⠀⣀⣴⠟⠁⡠⣴⡇⡸⠁⠀⢠⣾⣿⣿⣿⣷⣠⠀⠀⠀⠀⠀⠀⠀⢼⣿⣿⣿⣿⣦⠀ ⠀⢸⠹⣷⣄⠀⠙⣿⡀⠀⠀⠀⠀
                ⠀⠀⢰⡞⠉⠁⠀⠤⠊⢠⡿⢱⠇⠀⠐⢛⡿⠿⠿⢿⡟⠁⠀⠀⠀⠀⠀⠀⠀⠈⢿⠛⣿⣿⠛⠁⠀⠹⡷⣿⡇⠳⢄⡈⠳⢶⣦⡀⠀
                ⠀⠠⣾⠃⠀⡀⠀⠀⠀⢸⡇⣿⠀⠀⠀⠀⠀⠀⣠⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢢⠀⠀⠀⠀⠀⠀⠹⣿⡇⠀⢄⢈⠢⣀⣿⡷⠦
                ⠀⣼⡷⠀⢀⠔⠂⡰⠁⢈⡇⡇⠀⠀⠀⠀⢀⡴⠁⠀⠀⣠⣶⣶⣿⣿⣿⣶⣦⡀⠀⠀⠳⡀⠀⠀⠀⠀⠀⣿⣧⡀⠀⡙⠱⣌⢻⣿⡂
                ⠰⢿⣧⠞⢁⡤⠊⠀⠀⣼⣇⡇⠀⡠⠔⠊⠁⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀⠀⠀⠈⠑⠢⢄⠀⢠⣿⡟⡇⠠⡘⢦⠈⢺⣯⠁
                ⠀⠸⣿⠶⠋⣠⠎⢀⡞⠙⣿⡇⠀⡇⣸⡀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀⠀⣀⠈⡆⣸⣿⡻⠀⠀⠻⣄⡳⣼⣿⡀
                ⠀⠀⢿⣶⠏⢁⣶⠟⠀⠀⣿⣧⠀⠀⣿⣿⡄⠀⠀⠀⠀⠀⠈⠉⢻⣿⣛⠉⠀⠀⠀⠀⠀⢠⣾⣿⡆⠁⣿⡟⡇⠀⣦⡑⠂⣱⣿⣿⠇
                ⠀⠀⠈⢻⣷⡊⠀⢀⣀⢤⢿⡟⢴⠄⠘⣻⣿⣄⡀⠀⠀⠀⣀⣠⢿⡿⣄⣀⡀⠀⠀⠠⣴⢿⣿⡿⠁⢰⣿⡇⢣⠀⢌⣣⣷⠟⠁⠀⠀
                ⠀⠀⠀⠀⠙⣿⣿⣋⡿⢫⣿⣧⣰⠀⠀⢇⢻⣏⠉⡛⡟⠋⠉⠀⢸⡇⠀⠉⠉⣻⣿⠟⠁⢰⡟⠀⠀⣼⣿⣇⢠⡇⣸⠟⠏⠀⠀⠀⠀
                ⠀⠀⠀⠀⠀⠘⠿⠿⠶⣿⢿⣿⡏⡄⠀⠈⣶⢿⡀⢸⣷⠀⠀⠀⠸⠀⠀⠀⢀⣿⡟⠀⢠⡿⠀⠀⣄⠹⠻⣿⣄⣹⠏⠀⠀⠀⠀⠀⠀
                ⠀⠀⠀⠀⠀⠀⠀⣰⢸⡏⠀⢼⡟⢡⡀⠀⠸⣈⢷⡈⢻⡄⠀⠀⠀⠀⠀⠀⢸⡟⠁⢠⣿⠃⢸⣾⣿⠀⠀⢻⡙⠏⠀⠀⠀⠀⠀⠀⠀
                ⠀⠀⠀⠀⠀⠀⠀⢉⢸⠁⠀⠘⢇⣾⠁⠀⠀⠙⡆⠳⡌⢷⡀⠀⠀⠀⠀⣠⡟⣠⣶⡿⠃⠈⡈⠛⣇⠀⠀⢸⠧⠀⠀⠀⠀⠀⠀⠀⠀
                ⠀⠀⠀⠀⠀⠀⠀⢸⣸⡆⠀⠀⢸⣡⣶⣇⠀⠀⠈⢦⡙⢦⡛⠶⠦⠤⠖⣫⣾⣿⡿⠀⣤⢠⣇⠀⠁⠀⢠⢿⡀⠀⠀⠀⠀⠀⠀⠀⠀
                ⠀⠀⠀⠀⠀⠀⠀⠀⣏⢿⡄⠀⠘⢻⣿⠿⡇⠀⠀⠀⠉⠪⣿⣿⣶⣶⣾⣟⡩⠀⠀⠀⣿⣼⡟⠀⠀⠀⡞⣤⠇⠀⠀⠀⠀⠀⠀⠀⠀
                ⠀⠀⠀⠀⠀⠀⠀⠀⠘⡌⣷⡀⠀⠈⢻⣴⣷⣶⠀⠀⠀⡀⠀⠉⠚⠓⠚⠁⠀⠀⠀⠐⣿⠿⠀⠀⠀⡸⢁⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀
                ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣎⠃⠀⠀⠀⠋⢃⣸⡺⠂⠀⣧⡼⢷⡄⢠⣄⡄⢀⣼⡟⣰⠻⠀⠀⠀⡰⢡⣿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀
                ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠣⡀⠀⠀⠀⠛⠙⠁⠀⠘⠛⠁⢻⣿⠋⣿⡧⠈⢈⡴⠁⠀⠀⠀⠀⢁⠜⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
                ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⡞⠉⠀⠙⠁⠰⠋⠀⠀⠀⠀⠀⠴⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
                ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
                ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
                ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠐⠀⠒⠲⠀⠀⡀⠰⠐⠁⠐⡀⠃⠀⠀
*/

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