oj.uz

Submission #857514

# Submission time Handle Problem Language Result Execution time Memory
857514 2023-10-06T10:24:31 Z Trisanu_Das Radio (COCI22_radio) C++17
40 / 110
 355 ms 59984 KB 
#include <bits/stdc++.h>
using namespace std;
 
void solve1(int n, int q){
    vector<bool> v(n+1);
    for (int i = 0; i < q; ++i){
        char t; cin >> t;
        if (t == 'S') {
            int x; cin >> x;
            v[x] = !v[x];
        } else{
            int l, r; cin >> l >> r;
            bool flag = true;
            for (int j = l; j <= r; ++j){
                if (!v[j]) continue;
                for (int f = j + 1; f <= r; ++f){
                    if (!v[f]) continue;
                    if (__gcd(j, f) > 1) flag = false;
                }
            }
 
            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);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 6236 KB Output is correct
2 Correct 220 ms 29956 KB Output is correct
3 Correct 355 ms 59984 KB Output is correct
4 Correct 16 ms 6236 KB Output is correct
5 Correct 151 ms 30124 KB Output is correct
6 Correct 315 ms 59952 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 56 ms 6236 KB Output is correct
9 Correct 220 ms 29956 KB Output is correct
10 Correct 355 ms 59984 KB Output is correct
11 Correct 16 ms 6236 KB Output is correct
12 Correct 151 ms 30124 KB Output is correct
13 Correct 315 ms 59952 KB Output is correct
14 Incorrect 71 ms 1708 KB Output isn't correct
15 Halted 0 ms 0 KB -