oj.uz

답안 #857669

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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";
            }
        }
    } 
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 283 ms 104708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 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

Subtask #3
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 283 ms 104708 KB Output isn't correct
2 Halted 0 ms 0 KB -