oj.uz

Submission #963251

# Submission time Handle Problem Language Result Execution time Memory
963251 2024-04-14T19:23:11 Z Pety Radio (COCI22_radio) C++14
30 / 110
 744 ms 143188 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 371 ms 102920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 111684 KB Output is correct
2 Correct 676 ms 129348 KB Output is correct
3 Correct 744 ms 143188 KB Output is correct
4 Correct 335 ms 105052 KB Output is correct
5 Correct 355 ms 114040 KB Output is correct
6 Correct 445 ms 125028 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 371 ms 102920 KB Output isn't correct
2 Halted 0 ms 0 KB -