oj.uz

Submission #555119

# Submission time Handle Problem Language Result Execution time Memory
555119 2022-04-30T07:50:30 Z snasibov05 Radio (COCI22_radio) C++14
40 / 110
 441 ms 59984 KB 
#include <bits/stdc++.h>

using namespace std;

int gcd(int a, int b){
    while (b){
        a %= b;
        swap(a, b);
    }
    return a;
}

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 <= 100) solve1(n, q);
    else solve2(n, q);


    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 6232 KB Output is correct
2 Correct 255 ms 29928 KB Output is correct
3 Correct 441 ms 59984 KB Output is correct
4 Correct 22 ms 6100 KB Output is correct
5 Correct 195 ms 29924 KB Output is correct
6 Correct 404 ms 59972 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 82 ms 6232 KB Output is correct
9 Correct 255 ms 29928 KB Output is correct
10 Correct 441 ms 59984 KB Output is correct
11 Correct 22 ms 6100 KB Output is correct
12 Correct 195 ms 29924 KB Output is correct
13 Correct 404 ms 59972 KB Output is correct
14 Incorrect 90 ms 460 KB Output isn't correct
15 Halted 0 ms 0 KB -