oj.uz

Submission #555332

# Submission time Handle Problem Language Result Execution time Memory
555332 2022-04-30T13:03:39 Z Mamedov Radio (COCI22_radio) C++17
110 / 110
 1061 ms 144528 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 18764 KB Output is correct
2 Correct 678 ms 76736 KB Output is correct
3 Correct 945 ms 141004 KB Output is correct
4 Correct 24 ms 12628 KB Output is correct
5 Correct 205 ms 61960 KB Output is correct
6 Correct 444 ms 123212 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 317 ms 18764 KB Output is correct
9 Correct 678 ms 76736 KB Output is correct
10 Correct 945 ms 141004 KB Output is correct
11 Correct 24 ms 12628 KB Output is correct
12 Correct 205 ms 61960 KB Output is correct
13 Correct 444 ms 123212 KB Output is correct
14 Correct 209 ms 1360 KB Output is correct
15 Correct 420 ms 10936 KB Output is correct
16 Correct 1061 ms 144528 KB Output is correct
17 Correct 938 ms 141060 KB Output is correct
18 Correct 1041 ms 142784 KB Output is correct
19 Correct 967 ms 142932 KB Output is correct
20 Correct 430 ms 124048 KB Output is correct
21 Correct 440 ms 124072 KB Output is correct
22 Correct 435 ms 123960 KB Output is correct
23 Correct 450 ms 123964 KB Output is correct