# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
857511 | 2023-10-06T10:22:49 Z | Trisanu_Das | Radio (COCI22_radio) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; void solve1(int n, int q){ bool a[n + 1]; memset(a, false, sizeof(a)); while(q--) { char t; cin >> t; if (t == 'S') { int x; cin >> x; v[x] = !v[x]; }else{ int x, y; cin >> x >> y; bool ans = true; for (int i = x; i <= y; i++){ if (!a[i]) continue; for (int j = i + 1; j <= r; j++){ if (a[f] && __gcd(i, j) > 1) { ans = false; break; } } if(ans) break; } if (flag) cout << "NE\n"; else cout << "DA\n"; } } } void solve2(int n, int q){ vector<vector<int>> prime(n + 1); for (int i = 2; i <= n; ++i){ if (!prime[i].empty()) continue; for (int j = i; j <= n; j += i){ prime[j].push_back(i); } } vector<int> cnt(n+1); vector<bool> active(n+1); int k = 0; for (int i = 0; i < q; ++i){ char t; cin >> t; if (t == 'S') { int x; cin >> x; if (!active[x]) { for (auto p : prime[x]) { cnt[p]++; if (cnt[p] == 2) k++; } } else{ for (auto p : prime[x]){ cnt[p]--; if (cnt[p] == 1) k--; } } active[x] = !active[x]; } else{ int l, r; cin >> l >> r; if (k > 0) cout << "DA\n"; else cout << "NE\n"; } } } int main() { int n, q; cin >> n >> q; if (n < 101) solve1(n, q); else solve2(n, q); }