Submission #980596

#TimeUsernameProblemLanguageResultExecution timeMemory
980596SamNguyenRadio (COCI22_radio)C++14
10 / 110
1542 ms108628 KiB
#include <bits/stdc++.h> using namespace std; template <class T> inline bool MINIMISE(T &x, T y) { if (x > y) { x = y; return true; } return false; } template <class T> inline bool MAXIMISE(T &x, T y) { if (x < y) { x = y; return true; } return false; } template <class T, class F> void UNSAFE_FOR_LEFT_RIGHT(set<T> &x, T v, F f) { auto it = x.lower_bound(v); f(*prev(it), *it); } template <class T, int N> class SegmentTree { private: int n, st[4 * N]; function<T(T, T)> fn_combine; T ZERO; void build(int id, int l, int r, int arr[]) { if (l == r) { st[id] = arr[r]; return; } int m = (l + r) >> 1; build(id << 1, l, m, arr); build(id << 1 | 1, m + 1, r, arr); st[id] = fn_combine(st[id << 1], st[id << 1 | 1]); } void update(int id, int l, int r, int i, int v) { if (r < i or i < l) return; if (l == r) { st[id] = v; return; } int m = (l + r) >> 1; update(id << 1, l, m, i, v); update(id << 1 | 1, m + 1, r, i, v); st[id] = fn_combine(st[id << 1], st[id << 1 | 1]); } int query(int id, int l, int r, int left, int right) { if (r < left or right < l) return ZERO; if (left <= l and r <= right) return st[id]; int m = (l + r) >> 1; return fn_combine( query(id << 1, l, m, left, right), query(id << 1 | 1, m + 1, r, left, right) ); } public: void init(int _n, function<T(T, T)> _fn, T _zero) { n = _n; fn_combine = _fn; ZERO = _zero; fill(st, st + 4 * n, ZERO); } void init(int _n, function<T(T, T)> _fn, T _zero, T arr[]) { n = _n; fn_combine = _fn; ZERO = _zero; build(1, 1, n, arr); } void update(int i, T v) { update(1, 1, n, i, v); } T query(T left, T right) { return query(1, 1, n, left, right); } }; #define INPFILE "coci21c5p4.inp" #define OUTFILE "coci21c5p4.out" const int MAX = 1e6 + 7; int PF[MAX]; void sieve() { iota(PF, PF + MAX, 0); for (int i = 2; i * i < MAX; i++) if (PF[i] == i) for (int j = i * i; j < MAX; j += i) PF[j] = i; } template <class F> void FOR_PRIMES_UPTO(int N, F f) { for (int v = 2; v <= N; v++) if (PF[v] == v) f(v); } template <class F> void FOR_FACTORS(int n, F f) { while (n > 1) { int p = PF[n], c = 0; while (n % p == 0) n /= p, c++; f(p, c); } } int N, Q; SegmentTree<int, MAX> st_left, st_right; bool is_online[MAX]; set<int> inds[MAX]; void init() { st_left .init(N, [](int x, int y) { return max(x, y); }, -MAX); st_right.init(N, [](int x, int y) { return min(x, y); }, +MAX); FOR_PRIMES_UPTO(N, [&](int p) { inds[p].insert(-MAX); inds[p].insert(+MAX); }); memset(is_online, false, sizeof is_online); } void update_position(int i) { int li = -MAX, ri = +MAX; if (is_online[i]) FOR_FACTORS(i, [&](int p, int c) { UNSAFE_FOR_LEFT_RIGHT(inds[p], i, [&](int l, int r) { // cerr << "p = " << p << " -> update " << l << " <-> " << i << " <-> " << r << endl; MAXIMISE(li, l); MINIMISE(ri, r); }); }); st_left .update(i, li); st_right.update(i, ri); } void update(int x) { is_online[x] ^= 1; if (not is_online[x]) FOR_FACTORS(x, [&](int p, int c) { inds[p].erase(x); }); vector<int> candidates; FOR_FACTORS(x, [&](int p, int c) { UNSAFE_FOR_LEFT_RIGHT(inds[p], x, [&](int l, int r) { // cerr << "p = " << p << " -> " << l << " " << r << endl; if (l >= 1 and l < x) candidates.push_back(l); if (r > x and r <= N) candidates.push_back(r); }); }); update_position(x); if (is_online[x]) FOR_FACTORS(x, [&](int p, int c) { inds[p].insert(x); }); for (int i : candidates) update_position(i); // cerr << "lefts: "; // for (int i = 1; i <= N; i++) // cerr << st_left.query(i, i) << " "; // cerr << endl; // cerr << "rights: "; // for (int i = 1; i <= N; i++) // cerr << st_right.query(i, i) << " "; // cerr << endl; } bool query(int l, int r) { // cerr << "max_left = " << st_left .query(l, r) << endl; // cerr << "min_right = " << st_right.query(l, r) << endl; return st_right.query(l, r) <= r and st_left .query(l, r) >= l; } int main(void) { if (fopen(INPFILE, "r")) { freopen(INPFILE, "r", stdin); freopen(OUTFILE, "w", stdout); } ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); sieve(); cin >> N >> Q; init(); while (Q--) { char t; cin >> t; if (t == 'S') { int x; cin >> x; update(x); } else { int l, r; cin >> l >> r; cout << (query(l, r) ? "DA" : "NE") << '\n'; } } return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:198:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  198 |   freopen(INPFILE, "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:199:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  199 |   freopen(OUTFILE, "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...