Submission #1058339

#TimeUsernameProblemLanguageResultExecution timeMemory
1058339manhlinh1501Radio (COCI22_radio)C++17
110 / 110
323 ms92072 KiB
#include<bits/stdc++.h> using namespace std; using i64 = long long; const int MAXN = 1e6 + 5; const int oo32 = 1e9; #define ALL(a) (a).begin(), (a).end() int N, Q; int prime[MAXN]; set<int> save[MAXN]; bool appear[MAXN]; int cur[MAXN]; struct segment_tree { int N; int tree[MAXN * 4]; void init(int _N) { N = _N; for(int i = 1; i <= 4 * N; i++) tree[i] = oo32; } void update(int p, int x) { int id = 1, l = 1, r = N; while(l < r) { int m = (l + r) / 2; if(p <= m) { id = id * 2; r = m; } else { id = id * 2 + 1; l = m + 1; } } tree[id] = x; while(id >= 1) { id >>= 1; tree[id] = min(tree[id * 2], tree[id * 2 + 1]); } } int get(int id, int l, int r, int u, int v) { if(r < u or l > v) return oo32; if(u <= l and r <= v) return tree[id]; int m = (l + r) / 2; return min(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v)); } int get(int l, int r) { return get(1, 1, N, l, r); } } ST; void sieve() { iota(prime, prime + MAXN + 1, 0); for(int i = 2; i * i < MAXN; i++) { if(prime[i] == i) { for(int j = i * i; j < MAXN; j += i) prime[j] = i; } } } void add(int z) { int x = z; appear[z] = true; while(x > 1) { int p = prime[x]; save[p].emplace(z); auto low = save[p].lower_bound(z); if(low != save[p].begin()) { low--; if(cur[*low] > z) { ST.update(*low, z); cur[*low] = z; } } auto high = save[p].upper_bound(z); if(high != save[p].end()) { if(cur[z] > *high) { ST.update(z, *high); cur[z] = *high; } } while(x % p == 0) x /= p; } } void del(int x) { vector<int> temp; int tmp_x = x; while (tmp_x > 1) { int p = prime[tmp_x]; auto it = save[p].lower_bound(x); if (it != save[p].begin()) { it--; if (cur[*it] == x) temp.push_back(*it); } while (tmp_x % p == 0) tmp_x /= p; save[p].erase(x); } cur[x] = oo32; ST.update(x, oo32); // sort(ALL(temp)); // temp.resize(unique(ALL(temp)) - temp.begin()); for (auto u : temp) { cur[u] = oo32; ST.update(u, oo32); } for (auto u : temp) add(u); appear[x] = false; } signed main() { if(fopen("code.inp", "r")) { freopen("code.inp", "r", stdin); freopen("code.out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); sieve(); cin >> N >> Q; ST.init(N); for(int i = 0; i < MAXN; i++) cur[i] = oo32; while(Q--) { char type; cin >> type; if(type == 'S') { int x; cin >> x; if(appear[x] == false) add(x); else del(x); } else { int l, r; cin >> l >> r; int x = ST.get(l, r); cout << (x <= r ? "DA" : "NE") << "\n"; } } }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen("code.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen("code.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void sieve()':
Main.cpp:54:9: warning: array subscript 1000006 is outside array bounds of 'int [1000005]' [-Warray-bounds]
   54 |     iota(prime, prime + MAXN + 1, 0);
      |     ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:8:5: note: while referencing 'prime'
    8 | int prime[MAXN];
      |     ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...