Submission #881019

#TimeUsernameProblemLanguageResultExecution timeMemory
881019Cyber_WolfRadio (COCI22_radio)C++17
0 / 110
255 ms128424 KiB
#include <bits/stdc++.h> using namespace std; #define lg long long #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define mid (lr+hr)/2 const lg N = 1e6+5; set<lg> se[N]; bitset<N> vis; lg l[N][7], r[N][7], seg[N << 2][2]; map<lg, lg> mp[N]; void build(lg node, lg lr, lg hr) { if(lr == hr) { seg[node][0] = 1e9; seg[node][1] = -1e9; return; } build(node << 1, lr, mid); build(node << 1 | 1, mid+1, hr); seg[node][0] = min(seg[node << 1][0], seg[node << 1 | 1][0]); seg[node][1] = max(seg[node << 1][1], seg[node << 1 | 1][1]); return; } void update(lg node, lg lr, lg hr, lg idx) { if(lr > idx || idx < hr) return; if(lr == hr) { seg[node][0] = 1e9; for(int i = 0; i < 7; i++) { seg[node][0] = min(seg[node][0], r[idx][i]); } seg[node][1] = -1e9; for(int i = 0; i < 7; i++) { seg[node][1] = max(seg[node][1], l[idx][i]); } return; } update(node << 1, lr, mid, idx); update(node << 1 | 1, mid+1, hr, idx); seg[node][0] = min(seg[node << 1][0], seg[node << 1 | 1][0]); seg[node][1] = max(seg[node << 1][1], seg[node << 1 | 1][1]); return ; } array<lg, 2> get(lg node, lg lr, lg hr, lg lq, lg hq) { if(lq <= lr && hr <= hq) return {seg[node][0], seg[node][1]}; array<lg, 2> a = {(lg)1e9, -(lg)1e9}; if(lr > hq || lq > hr) return a; array<lg, 2> b = get(node << 1, lr, mid, lq, hq); a = get(node << 1 | 1, mid+1, hr, lq, hq); a[0] = min(a[0], b[0]); a[1] = max(a[1], b[1]); return a; } signed main() { fastio; lg n, q; cin >> n >> q; build(1, 1, n); while(q--) { char c; cin >> c; if(c == 'S') { lg x; cin >> x; lg z = x; bool del = (!vis[x]); vis[x] = true; vector<lg> o; for(lg i = 2; i*i <= x; i++) { while(x%i == 0) { if(o.empty() || o.back() != i) { mp[z][i] = o.size(); o.push_back(i); } x /= i; } } if(x > 1) { mp[z][x] = o.size(); o.push_back(x); } if(del) { for(int i = 0; i < o.size(); i++) { auto nxt = se[o[i]].upper_bound(z); auto prv = se[o[i]].lower_bound(z); if(nxt != se[o[i]].end()) { lg j = mp[*nxt][o[i]]; l[*nxt][j] = l[z][i]; update(1, 1, n, *nxt); l[z][i] = -1e9; } if(prv != se[o[i]].begin()) { prv--; lg k = mp[*prv][o[i]]; r[*prv][k] = r[z][i]; update(1, 1, n, (*prv)); r[z][i] = 1e9; } update(1, 1, n, z); se[o[i]].erase(z); } } else{ for(int i = 0; i < o.size(); i++) { auto nxt = se[o[i]].upper_bound(z); auto prv = se[o[i]].lower_bound(z); if(nxt != se[o[i]].end()) { lg j = mp[*nxt][o[i]]; l[*nxt][j] = i; r[z][i] = (*nxt); update(1, 1, n, (*nxt)); } if(prv != se[o[i]].begin()) { prv--; lg k = mp[*prv][o[i]]; r[*prv][k] = i; l[z][i] = (*prv); update(1, 1, n, (*prv)); } update(1, 1, n, z); se[o[i]].insert(z); } } } else if(c == 'C') { lg l, r; cin >> l >> r; array<lg, 2> ans = get(1, 1, n, l, r); cout << (ans[0] <= r || ans[1] >= l ? "DA\n" : "NE\n"); } } }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:104:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     for(int i = 0; i < o.size(); i++)
      |                    ~~^~~~~~~~~~
Main.cpp:128:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for(int i = 0; i < o.size(); i++)
      |                    ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...