Submission #541911

#	Time	Username	Problem	Language	Result	Execution time	Memory
541911		Alex_tz307	Radio (COCI22_radio)	C++17	110 / 110	1345 ms	248284 KiB

Main

#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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70