oj.uz

Submission #798933

# Submission time Handle Problem Language Result Execution time Memory
798933 2023-07-31T07:40:17 Z makanhulia Radio (COCI22_radio) C++17
30 / 110
 621 ms 115904 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 243 ms 89300 KB Output is correct
2 Correct 500 ms 105696 KB Output is correct
3 Correct 621 ms 115904 KB Output is correct
4 Correct 42 ms 80196 KB Output is correct
5 Correct 76 ms 85212 KB Output is correct
6 Correct 125 ms 91724 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 -