제출 #857669

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
857669		TahirAliyev	Radio (COCI22_radio)	C++17	30 / 110	567 ms	122660 KiB

Main

#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";
            }
        }
    } 
}

• Subtask 1: 0 / 10
• Subtask 2: 30 / 30
• Subtask 3: 0 / 70