Submission #857669

# Submission time Handle Problem Language Result Execution time Memory
857669 2023-10-06T15:15:18 Z TahirAliyev Radio (COCI22_radio) C++17
30 / 110
567 ms 122660 KB
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long int
#define oo 1e17
#define pii pair<int, int>

const int MAX = 1e6 + 6;
int n, q;
set<int> p[MAX];
bool isOn[MAX];


vector<int> factors[MAX];
bool isP[MAX];

void sieve(){
    memset(isP, 1, sizeof(isP));
    for(int i = 2; i < MAX; i++){
        if(!isP[i]) continue;
        factors[i].push_back(i);
        for(int j = i + i; j < MAX; j += i){
            factors[j].push_back(i);
            isP[j] = 0;
        }
    }
}

int main(){
    sieve();
    cin >> n >> q;
    int anscnt = 0;
    while(q--){
        string t; cin >> t;
        if(t[0] == 'S'){
            int x; cin >> x;
            if(!isOn[x]){
                for(int a : factors[x]){
                    p[a].insert(x);
                    if(p[a].size() == 2){
                        anscnt++;
                    }
                }
                isOn[x] = 1;
            }
            else{
                for(int a : factors[x]){
                    p[a].erase(x);
                    if(p[a].size() == 1){
                        anscnt--;
                    }
                }
                isOn[x] = 0;
            }
        }
        else{
            int l, r; cin >> l >> r;
            if(anscnt){
                cout << "DA\n";
            }
            else{
                cout << "NE\n";
            }
        }
    } 
}
# Verdict Execution time Memory Grader output
1 Incorrect 283 ms 104708 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 430 ms 110484 KB Output is correct
2 Correct 567 ms 119376 KB Output is correct
3 Correct 561 ms 122660 KB Output is correct
4 Correct 288 ms 104788 KB Output is correct
5 Correct 313 ms 104688 KB Output is correct
6 Correct 351 ms 104724 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 283 ms 104708 KB Output isn't correct
2 Halted 0 ms 0 KB -