oj.uz

Submission #798927

# Submission time Handle Problem Language Result Execution time Memory
798927 2023-07-31T07:31:48 Z makanhulia Radio (COCI22_radio) C++17
30 / 110
 661 ms 117232 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
 
const int N = 1e6 + 5;

int a[N], st[4 * N], sieve[N];
bool check[N];
priority_queue<int> pq[N];
set<int> s[N];

int merge(int x, int y) {
    return min(x, y);
}
 
void build(int x, int tl, int tr) {
    if (tl == tr) st[x] = 1e9;
    else {
        int tm = (tl + tr) / 2;
        build(2 * x, tl, tm);
        build(2 * x + 1, tm + 1, tr);
        st[x] = 1e9;
    }
}
 
void update(int x, int tl, int tr, int pos) {
    if (tl == tr) {
      if (!check[pos]) {
        st[x] = 1e9;
        return;
      }
      while (!pq[pos].empty() and !check[-pq[pos].top()]) pq[pos].pop();
      if (pq[pos].empty()) st[x] = 1e9;
      else st[x] = -pq[pos].top();
    }
    else {
        int tm = (tl + tr) / 2;
        if (pos <= tm) update(2 * x, tl, tm, pos);
        else update(2 * x + 1, tm + 1, tr, pos);
        st[x] = merge(st[2 * x], st[2 * x + 1]);
    }
}
 
int get(int x, int tl, int tr, int l, int r) {
    if (l <= tl and tr <= r) return st[x];
    if (r < tl or l > tr) return 1e9;
    int tm = (tl + tr) / 2;
    return merge(get(2 * x, tl, tm, l, r), get(2 * x + 1, tm + 1, tr, l, r));
}
 
int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    for (int i = 2; i * i <= n; i++) {
      if (sieve[i] != 0) continue;
      for (int j = i; j <= n; j += i) if (sieve[j] == 0) sieve[j] = i;
    }
    for (int i = 2; i <= n; i++) if (sieve[i] == 0) sieve[i] = i;
    build(1, 1, n);
    while (q--) {
      char c;
      cin >> c;
      if (c == 'S') {
        int x;
        cin >> x;
        if (x == 1) continue;
        if (check[x]) {
          check[x] = 0;
          update(1, 1, n, x);
          int tm = x;
          while (tm > 1) {
            int tm2 = sieve[tm];
            while (tm % tm2 == 0) tm /= tm2;
            s[tm2].erase(x);
            if (s[tm2].empty()) continue;
            auto it = s[tm2].upper_bound(x), it2 = it;
            if (it != s[tm2].begin()) {
              it--;
              pq[*it].push(-*it2);
            }
            update(1, 1, n, *it);
          }
        }
        else {
          check[x] = 1;
          int tm = x;
          while (tm > 1) {
            int tm2 = sieve[tm];
            while (tm % tm2 == 0) tm /= tm2;
            if (s[tm2].empty()) {
              s[tm2].insert(x);
              continue;
            }
            auto it = s[tm2].upper_bound(x);
            if (it != s[tm2].begin()) {
              it--;
              pq[*it].push(-x);
              update(1, 1, n, *it);
              it++;
            }
            if (it != s[tm2].end()) pq[x].push(-*it);
            s[tm2].insert(x);
          }
          update(1, 1, n, x);
        }
      }
      else {
        int l, r;
        cin >> l >> r;
        int ans = get(1, 1, n, l, r);
        if (ans > r) cout << "NE\n";
        else cout << "DA\n";
      }
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 78548 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 256 ms 90164 KB Output is correct
2 Correct 612 ms 106856 KB Output is correct
3 Correct 661 ms 117232 KB Output is correct
4 Correct 43 ms 80284 KB Output is correct
5 Correct 78 ms 85920 KB Output is correct
6 Correct 124 ms 93200 KB Output is correct

Subtask #3
0 / 70.0

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