Submission #1058114

#TimeUsernameProblemLanguageResultExecution timeMemory
1058114manhlinh1501Radio (COCI22_radio)C++17
10 / 110
226 ms428608 KiB
#include<bits/stdc++.h> using namespace std; using i64 = long long; const int MAXN = 1e6 + 5; const int MAXP = 170; int N, Q; int prime[MAXN]; vector<int> vp; int cnt[MAXN]; bool appear[MAXN]; struct fenwick { int tree[MAXN]; void update(int x, int v) { for(; x < MAXN; x += (x & -x)) tree[x] += v; } int calc(int x) { int res = 0; for(; x; x -= (x & -x)) res += tree[x]; return res; } int range(int l, int r) { return calc(r) - calc(l - 1); } } BIT[MAXP]; void sieve() { iota(prime, prime + MAXN + 1, 0); for(int i = 2; i * i < MAXN; i++) { if(prime[i] == i) { for(int j = i * i; j < MAXN; j += i) prime[j] = i; } } for(int i = 2; i * i < MAXN; i++) { if(i == prime[i]) vp.emplace_back(i); } cerr << vp.size(); } signed main() { if(fopen("code.inp", "r")) { freopen("code.inp", "r", stdin); freopen("code.out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); sieve(); cin >> N >> Q; while(Q--) { char type; cin >> type; if(type == 'S') { int x; cin >> x; for(int i = 0; i < vp.size(); i++) { if(x % vp[i] == 0) { BIT[i].update(x, (appear[x] == true ? -1 : 1)); } } appear[x] ^= 1; } else { int l, r; cin >> l >> r; bool ok = true; for(int i = 0; i < vp.size(); i++) { if(BIT[i].range(l, r) > 1) ok = false; } cout << (ok ? "NE" : "DA") << "\n"; } } }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:64:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             for(int i = 0; i < vp.size(); i++) {
      |                            ~~^~~~~~~~~~~
Main.cpp:74:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             for(int i = 0; i < vp.size(); i++) {
      |                            ~~^~~~~~~~~~~
Main.cpp:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         freopen("code.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         freopen("code.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void sieve()':
Main.cpp:34:9: warning: array subscript 1000006 is outside array bounds of 'int [1000005]' [-Warray-bounds]
   34 |     iota(prime, prime + MAXN + 1, 0);
      |     ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:8:5: note: while referencing 'prime'
    8 | int prime[MAXN];
      |     ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...