Submission #798887

#	Time	Username	Problem	Language	Result	Execution time	Memory
798887		devariaota	Radio (COCI22_radio)	C++17	30 / 110	610 ms	117316 KiB

Main

#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;
            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);
            it--;
            pq[*it].push(-x);
            update(1, 1, n, *it);
            it++;
            if (it != s[tm2].end()) pq[x].push(-*it);
            s[tm2].insert(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
• Subtask 2: 30 / 30
• Subtask 3: 0 / 70