Submission #555332

#	Time	Username	Problem	Language	Result	Execution time	Memory
555332		Mamedov	Radio (COCI22_radio)	C++17	110 / 110	1061 ms	144528 KiB

Main

#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int up = 1e6 + 6;
int toRight[up], tree[up << 2];

void init(int n) {
  for (int i = 1; i <= n; ++i) {
    toRight[i] = oo;
  }
  for (int i = 1; i <= (n << 2); ++i) {
    tree[i] = oo;
  }
}

void update(int node, int l, int r, int pos) {
  if (l == r) {
    tree[node] = toRight[pos];
  } else {
    int mid = (l + r) >> 1;
    if (pos <= mid) update((node << 1), l, mid, pos);
    else update((node << 1) | 1, mid + 1, r, pos);
    tree[node] = min(tree[(node << 1)], tree[(node << 1) | 1]);
  }
}

int getMin(int node, int l, int r, int ql, int qr) {
  if (l > qr || ql > r) return oo;
  else if (ql <= l && r <= qr) {
    return tree[node];
  } else {
    int mid = (l + r) >> 1;
    return min(getMin((node << 1), l, mid, ql, qr), getMin((node << 1) | 1, mid + 1, r, ql, qr));
  }
}

void sieve(int n, vector<vector<int>> &pfactor) {
  vector<bool>isPrime(n + 1, true);
  for (int i = 2; i <= n; ++i) {
    if (isPrime[i]) {
      for (int j = i; j <= n; j += i) {
        pfactor[j].eb(i);
        isPrime[j] = false;
      }
    }
  }
}

void Add(int x, int n, vector<vector<int>> &pfactor, vector<set<int>> &group) {
  for (int p : pfactor[x]) {
    group[p].insert(x);
    auto itr = group[p].find(x);
    if (itr != group[p].begin()) {
      --itr;
      int prev = (*itr);
      if (toRight[prev] > x) {
        toRight[prev] = x;
        update(1, 1, n, prev);
      }
      ++itr;
    }
    ++itr;
    if (itr != group[p].end()) {
      int nxt = (*itr);
      if (toRight[x] > nxt) {
        toRight[x] = nxt;
        update(1, 1, n, x);
      }
    }
  }
}

void Del(int x, int n, vector<vector<int>> &pfactor, vector<set<int>> &group) {
  vector<int>wait;
  for (int p : pfactor[x]) {
    auto itr = group[p].find(x);
    if (itr != group[p].begin()) {
      --itr;
      wait.eb((*itr));
      ++itr;
    }
    group[p].erase(itr);
  }
  for (int w : wait) {
    toRight[w] = oo;
    for (int p : pfactor[w]) {
      auto itr = group[p].find(w);
      ++itr;
      if (itr != group[p].end()) {
        toRight[w] = min(toRight[w], (*itr));
      }
    }
    update(1, 1, n, w);
  }
  toRight[x] = oo;
  update(1, 1, n, x);
}
void solve() {
  int n, q;
  cin >> n >> q;
  init(n);
  vector<vector<int>> pfactor(n + 1);
  vector<bool>state(n + 1, false);
  vector<set<int>>group(n + 1);
  sieve(n, pfactor);
  char type;
  int l, r;
  while (q--) {
    cin >> type >> l;
    if (type == 'S') {
      if (state[l]) {
        Del(l, n, pfactor, group);
        state[l] = false;
      } else {
        Add(l, n, pfactor, group);
        state[l] = true;
      }
    } else {
      cin >> r;
      if (getMin(1, 1, n, l, r) <= r) {
        cout << "DA\n";
      } else {
        cout << "NE\n";
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);

  int t = 1;
  //cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

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