Submission #769970

#	Time	Username	Problem	Language	Result	Execution time	Memory
769970		gun_gan	Radio (COCI22_radio)	C++17	110 / 110	593 ms	93872 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
int n, q, spf[N];
set<int> pos[N];
bool b[N];

int t[4 * N], nxt[N];

void update(int v, int l, int r, int idx, int val) {
      if(l > idx || r < idx) return;
      if(l == r) {
            t[v] = val;
            return;
      }
      int mid = (l + r) / 2;
      update(v * 2, l, mid, idx, val);
      update(v * 2 + 1, mid + 1, r, idx, val);
      t[v] = min(t[v * 2], t[v * 2 + 1]);
}

int query(int v, int l, int r, int ql, int qr) {
      if(qr < l || ql > r) return 1e9;
      if(ql <= l && qr >= r) return t[v];
      int mid = (l + r) / 2;
      return min(query(v * 2, l, mid, ql, qr), query(v * 2 + 1, mid + 1, r, ql, qr));
}

int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);

      for(int i = 2; i < N; i++) {
            if(!spf[i]) {
                  for(int j = i; j < N; j += i) if(!spf[j]) spf[j] = i;
            }
      }

      for(int i = 1; i < 4 * N; i++) t[i] = 1e9;
      for(int i = 1; i < N; i++) nxt[i] = 1e9;

      cin >> n >> q;
      while(q--) {
            char c;
            cin >> c;
            if(c == 'S') {
                  int x;
                  cin >> x;

                  int t = x;
                  if(b[x]) {
                        while(x > 1) {
                              int s = spf[x];
                              while(x % s == 0) x /= s;
                              auto it = pos[s].upper_bound(t);
                              auto it2 = pos[s].lower_bound(t);

                              if(it2 != pos[s].begin()) {
                                    it2--;

                                    int to = 1e9;
                                    if(it != pos[s].end()) to = *it;
                                    if(nxt[*it2] == t) {
                                          int z = *it2;
                                          nxt[*it2] = to;

                                          while(z > 1) {
                                                int s = spf[z];
                                                while(z % s == 0) z /= s;
                                                auto it = pos[s].upper_bound(t);
                                                if(it != pos[s].end()) nxt[*it2] = min(nxt[*it2], *it);
                                          }

                                          update(1, 1, n, *it2, nxt[*it2]);
                                    }
                              }

                              pos[s].erase(t);
                        }

                        nxt[t] = 1e9; 
                        update(1, 1, n, t, nxt[t]);
                  } else {
                        while(x > 1) {
                              int s = spf[x];
                              while(x % s == 0) x /= s;
                              auto it = pos[s].upper_bound(t);
                              if(it != pos[s].end()) nxt[t] = min(nxt[t], *it);

                              if(it != pos[s].begin()) {
                                    it--;
                                    nxt[*it] = min(nxt[*it], t);
                                    update(1, 1, n, *it, nxt[*it]);
                              }
                              
                              pos[s].insert(t);
                        } 

                        update(1, 1, n, t, nxt[t]);
                  }

                  b[t] ^= 1;
            } else {
                  int l, r;
                  cin >> l >> r;

                  if(query(1, 1, n, l, r) <= r) {
                        cout << "DA\n";
                  } else {
                        cout << "NE\n";
                  }
            }
      }

}

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