oj.uz

Submission #541911

# Submission time Handle Problem Language Result Execution time Memory
541911 2022-03-24T19:33:32 Z Alex_tz307 Radio (COCI22_radio) C++17
110 / 110
 1345 ms 248284 KB 
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

const int kN = 1e6;
vector<int> primes[1 + kN];
set<int> pos[1 + kN];
multiset<int> R[1 + kN];
bitset<1 + kN> active;

void minSelf(int &x, int y) {
  if (y < x) {
    x = y;
  }
}

struct ST {
  int n;
  vector<int> t, leaf;

  void init(int N) {
    n = N;
    int dim = 1;
    while (dim < n) {
      dim *= 2;
    }
    t.resize(dim * 2, INF);
    leaf.resize(n + 1);
  }

  void build(int x, int lx, int rx) {
    if (lx == rx) {
      leaf[lx] = x;
      return;
    }
    int mid = (lx + rx) / 2;
    build(x * 2, lx, mid);
    build(x * 2 + 1, mid + 1, rx);
  }

  void update(int pos, int v) {
    int x = leaf[pos];
    t[x] = v;
    do {
      x /= 2;
      t[x] = min(t[x * 2], t[x * 2 + 1]);
    } while (x > 1);
  }

  int query(int x, int lx, int rx, int st, int dr) {
    if (st <= lx && rx <= dr) {
      return t[x];
    }
    int mid = (lx + rx) / 2, ans = INF;
    if (st <= mid) {
      minSelf(ans, query(x * 2, lx, mid, st, dr));
    }
    if (mid < dr) {
      minSelf(ans, query(x * 2 + 1, mid + 1, rx, st, dr));
    }
    return ans;
  }

  int query(int st, int dr) {
    return query(1, 1, n, st, dr);
  }
} t;

void precalc(int n) {
  for (int i = 2; i <= n; ++i) {
    if (primes[i].empty()) {
      for (int j = i; j <= n; j += i) {
        primes[j].emplace_back(i);
      }
    }
  }
}

void rem(int x) {
  active[x] = false;
  for (int p : primes[x]) {
    auto it = pos[p].lower_bound(x);
    int left = -1, right = -1;
    bool flag = false;
    if (it != pos[p].begin()) {
      --it;
      left = *it;
      if (x == *R[left].begin()) {
        flag = true;
      }
      R[left].erase(R[left].find(x));
    }
    it = pos[p].upper_bound(x);
    if (it != pos[p].end()) {
      right = *it;
    }
    if (left != -1 && right != -1) {
      if (right < *R[left].begin()) {
        flag = true;
      }
      R[left].emplace(right);
    }
    if (flag) {
      t.update(left, *R[left].begin());
    }
    pos[p].erase(x);
  }
  R[x] = {INF};
  t.update(x, INF);
}

void add(int x) {
  active[x] = true;
  for (int p : primes[x]) {
    auto it = pos[p].upper_bound(x);
    int v = -1;
    if (it != pos[p].end()) {
      v = *it;
      R[x].emplace(v);
    }
    if (it != pos[p].begin()) {
      --it;
      bool flag = false;
      if (x < *R[*it].begin()) {
        flag = true;
      }
      R[*it].emplace(x);
      if (v != -1) {
        R[*it].erase(R[*it].find(v));
      }
      if (flag) {
        t.update(*it, *R[*it].begin());
      }
    }
    pos[p].emplace(x);
  }
  t.update(x, *R[x].begin());
}

void testCase() {
  int n, q;
  cin >> n >> q;
  precalc(n);
  for (int i = 1; i <= n; ++i) {
    R[i].emplace(INF);
  }
  t.init(n);
  t.build(1, 1, n);
  for (int i = 0; i < q; ++i) {
    char ch;
    cin >> ch;
    if (ch == 'S') {
      int x;
      cin >> x;
      if (active[x]) {
        rem(x);
      } else {
        add(x);
      }
    } else {
      int l, r;
      cin >> l >> r;
      if (t.query(l, r) <= r) {
        cout << "DA\n";
      } else {
        cout << "NE\n";
      }
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 117708 KB Output is correct
2 Correct 50 ms 117732 KB Output is correct
3 Correct 51 ms 117692 KB Output is correct
4 Correct 52 ms 117736 KB Output is correct
5 Correct 54 ms 117692 KB Output is correct
6 Correct 50 ms 117732 KB Output is correct
7 Correct 51 ms 117656 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 138100 KB Output is correct
2 Correct 887 ms 191856 KB Output is correct
3 Correct 1170 ms 243484 KB Output is correct
4 Correct 76 ms 126988 KB Output is correct
5 Correct 262 ms 163384 KB Output is correct
6 Correct 515 ms 208972 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 117708 KB Output is correct
2 Correct 50 ms 117732 KB Output is correct
3 Correct 51 ms 117692 KB Output is correct
4 Correct 52 ms 117736 KB Output is correct
5 Correct 54 ms 117692 KB Output is correct
6 Correct 50 ms 117732 KB Output is correct
7 Correct 51 ms 117656 KB Output is correct
8 Correct 442 ms 138100 KB Output is correct
9 Correct 887 ms 191856 KB Output is correct
10 Correct 1170 ms 243484 KB Output is correct
11 Correct 76 ms 126988 KB Output is correct
12 Correct 262 ms 163384 KB Output is correct
13 Correct 515 ms 208972 KB Output is correct
14 Correct 215 ms 118232 KB Output is correct
15 Correct 563 ms 128520 KB Output is correct
16 Correct 1345 ms 248284 KB Output is correct
17 Correct 1102 ms 240680 KB Output is correct
18 Correct 1178 ms 244632 KB Output is correct
19 Correct 1176 ms 244464 KB Output is correct
20 Correct 511 ms 208980 KB Output is correct
21 Correct 520 ms 209104 KB Output is correct
22 Correct 531 ms 209096 KB Output is correct
23 Correct 522 ms 208964 KB Output is correct