Submission #542046

#TimeUsernameProblemLanguageResultExecution timeMemory
542046kamilszymczak11Radio (COCI22_radio)C++17
110 / 110
1006 ms145712 KiB
#include <iostream> #include <vector> #include <algorithm> #include <set> using namespace std; const int inf = 1 << 25; struct SegTree { vector<int>values; int leafCount; SegTree(int n) { for(leafCount = 1; leafCount < n; leafCount *= 2) {} values.resize(leafCount * 2, inf); } void Set(int x, int value) { x += leafCount; values[x] = value; for(x /= 2; x; x /= 2) values[x] = min(values[x * 2], values[x * 2 + 1]); } int GetMin(int a, int b) { a += leafCount; b += leafCount; int result = min(values[a], values[b]); for(; a / 2 != b / 2; a /= 2, b /= 2) { if(a % 2 == 0) result = min(result, values[a + 1]); if(b % 2 == 1) result = min(result, values[b - 1]); } return result; } }; void SwitchOn(int x, vector<int>&primeFactors, vector<set<int>>&s, vector<multiset<int>>&following, SegTree &T) { //cout << "switch on\n" << flush; for(int f : primeFactors) { auto it = s[f].insert(x).first; auto prev = it; auto next = it; next++; if(it != s[f].begin()) prev--; if(it != s[f].begin() && next != s[f].end()) { following[*prev].erase(following[*prev].find(*next)); if(following[*prev].empty()) T.Set(*prev, inf); else T.Set(*prev, *following[*prev].begin()); } if(it != s[f].begin()) { following[*prev].insert(x); if(following[*prev].empty()) T.Set(*prev, inf); else T.Set(*prev, *following[*prev].begin()); } if(next != s[f].end()) { following[x].insert(*next); } } if(following[x].empty()) T.Set(x, inf); else T.Set(x, *following[x].begin()); // cout << "done\n" << flush; } void SwitchOff(int x, vector<int>&primeFactors, vector<set<int>>&s, vector<multiset<int>>&following, SegTree &T) { //cout << "switch off\n" << flush; for(int f : primeFactors) { auto it = s[f].find(x); auto prev = it; auto next = it; next++; if(it != s[f].begin()) prev--; if(it != s[f].begin() && next != s[f].end()) { following[*prev].erase(following[*prev].find(x)); following[*prev].insert(*next); T.Set(*prev, *following[*prev].begin()); } if(it != s[f].begin() && next == s[f].end()) { following[*prev].erase(following[*prev].find(x)); if(following[*prev].empty()) T.Set(*prev, inf); else T.Set(*prev, *following[*prev].begin()); } s[f].erase(it); } following[x].clear(); T.Set(x, inf); // cout << "done\n" << flush; } int main() { ios_base::sync_with_stdio(0); int n, q; cin >> n >> q; vector<int>factor(n + 1, -1); for(int i = 2; i <= n; i++) { if(factor[i] == -1) { for(int j = i; j <= n; j += i) factor[j] = i; } } vector<set<int>>s(n + 1); vector<multiset<int>>next(n + 1); vector<bool>active(n + 1, false); SegTree T(n + 7); while(q--) { char c; cin >> c; if(c == 'S') { int x; cin >> x; if(x == 1) continue; vector<int>primeFactors; for(int y = x; y != 1; ) { primeFactors.push_back(factor[y]); int f = factor[y]; while(y % f == 0) y /= f; } if(active[x]) { SwitchOff(x, primeFactors, s, next, T); } else { SwitchOn(x, primeFactors, s, next, T); } active[x] = !active[x]; } else { int l, r; cin >> l >> r; int m = T.GetMin(l, r); if(m <= r) { cout << "DA\n"; } else { cout << "NE\n"; } } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...