제출 #881044

#제출 시각아이디문제언어결과실행 시간메모리
881044Cyber_WolfRadio (COCI22_radio)C++17
40 / 110
1540 ms233068 KiB
#include <bits/stdc++.h> using namespace std; #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define mid (lr+hr)/2 const int N = 1e6+5; set<int> se[N]; bitset<N> vis; int l[N][7], r[N][7], sz[N], seg[N << 2][2]; unordered_map<int, int> mp[N]; void build(int node, int lr, int 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(int node, int lr, int hr, int idx) { if(lr > idx || idx > hr) return; if(lr == hr) { seg[node][0] = 1e9; for(int i = 0; i < sz[idx]; i++) { seg[node][0] = min(seg[node][0], r[idx][i]); } seg[node][1] = -1e9; for(int i = 0; i < sz[idx]; 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<int, 2> get(int node, int lr, int hr, int lq, int hq) { if(lq <= lr && hr <= hq) return {seg[node][0], seg[node][1]}; array<int, 2> a = {(int)1e9, -(int)1e9}; if(lr > hq || lq > hr) return a; array<int, 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; int n, q; cin >> n >> q; for(int i = 0; i <= n; i++) for(int j = 0; j < 7; j++) l[i][j] = -1e9, r[i][j] = 1e9; build(1, 1, n); while(q--) { char c; cin >> c; if(c == 'S') { int x; cin >> x; int z = x; bool del = vis[x]; if(vis[x]) vis[x] = false; else vis[x] = true; vector<int> o; for(int 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); } sz[z] = o.size(); vector<int> up; 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()) { int j = mp[*nxt][o[i]]; l[*nxt][j] = l[z][i]; up.push_back((*nxt)); } if(prv != se[o[i]].begin()) { prv--; int k = mp[*prv][o[i]]; r[*prv][k] = r[z][i]; up.push_back((*prv)); } l[z][i] = -1e9; r[z][i] = 1e9; se[o[i]].erase(z); } } else{ // cout << z << '\n'; 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()) { int j = mp[*nxt][o[i]]; l[*nxt][j] = z; r[z][i] = (*nxt); up.push_back((*nxt)); } if(prv != se[o[i]].begin()) { prv--; int k = mp[*prv][o[i]]; r[*prv][k] = z; l[z][i] = (*prv); up.push_back((*prv)); } se[o[i]].insert(z); } } up.push_back(z); int lst = -1; for(auto it : up) { if(it == lst) continue; update(1, 1, n, it); lst = it; } } else if(c == 'C') { int l, r; cin >> l >> r; array<int, 2> ans = get(1, 1, n, l, r); cout << (ans[0] <= r || ans[1] >= l ? "DA\n" : "NE\n"); } } }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int i = 0; i < o.size(); i++)
      |                    ~~^~~~~~~~~~
Main.cpp:131:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     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...