Submission #963251

#	Time	Username	Problem	Language	Result	Execution time	Memory
963251		Pety	Radio (COCI22_radio)	C++14	30 / 110	744 ms	143188 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 2;
set<int>s[N];
vector<int>prim[N];
bitset<N>b;
bool on[N + 2];

int dr[N + 2];

int n, q;

template<typename T>
struct Aint {
  int n;
  vector<T>v;
	Aint(int N): n(N), v(4*N+2) {fill(v.begin(), v.end(), n + 1);}

  void build (T *a, int nod, int st, int dr) {
    if (st == dr) {
      v[nod] = (a + st);
      return;
    }
    int mid = (st + dr) / 2;
    build(2 * nod, st, mid);
    build(2 * nod + 1, mid + 1, dr);
    v[nod] = min(v[2 * nod],  v[2 * nod + 1]);
  }
  void update (int nod, int st, int dr, int poz, int val) {
    if (st == dr) {
      v[nod] = val;
      return;
    }
    int mid = (st + dr) / 2;
    if (poz <= mid)
      update(2 * nod, st, mid, poz, val);
    else 
      update(2 * nod + 1, mid + 1, dr, poz, val);
    v[nod] = min(v[2 * nod], v[2 * nod + 1]);
  }
  T query (int nod, int st, int dr, int a, int b) {
    if (a <= st && dr <= b) 
      return v[nod];
    int mid = (st + dr) / 2;
    if (b <= mid)
      return query(2 * nod, st, mid, a, b);
    else if (a > mid)
      return query(2 * nod + 1, mid + 1, dr, a, b);
    else
      return min(query(2 * nod, st, mid, a, b), query(2 * nod + 1, mid + 1, dr, a, b));
  }
};

void ciur () {
  for (int i = 2; i < N; i++)
    if (!b[i])
      for (int j = i; j < N; j += i) {
        b[j] = 1;
        prim[j].push_back(i);
      }
}

int main () 
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  ciur();
  cin >> n >> q;
  Aint<int> pom(n);
  fill(dr + 1, dr + n + 1, n + 1);
  while (q--) {
    char ch;
    cin >> ch;
    if (ch == 'S') {
      int x;
      cin >> x;

      if (!on[x]) {
        on[x] = 1;
        for (auto pr : prim[x]) {
          auto it = s[pr].lower_bound(x);
          if (it != s[pr].end())
            dr[x] = min(dr[x], *it);
          if (it != s[pr].begin()) {
            it--;
            if (dr[*it] > x) {
              dr[*it] = x;
              pom.update(1, 1, n, *it, x);
            }
          }
          s[pr].insert(x);
        }
        pom.update(1, 1, n, x, dr[x]);
      }
      else {
        on[x] = 0;
          for (auto pr : prim[x]) {
            s[pr].erase(x);
            auto it = s[pr].lower_bound(x);
            int val =  ((it != s[pr].end()) ? *it : n + 1);
            if (it != s[pr].begin()) {
              it--;
              pom.update(1, 1, n, *it, val);
            }
          }
        pom.update(1, 1, n, x, n + 1);
        dr[x] = n + 1;
      }
    }
    else {
      int l, r;
      cin >> l >> r;
      int plm = pom.query(1, 1, n, l, r);
      if (plm <= r) {
        cout << "DA\n";
      }
      else
        cout << "NE\n";
    }
  }
  return 0;
}

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