oj.uz

답안 #879978

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
879978 2023-11-28T12:41:17 Z HossamHero7 Radio (COCI22_radio) C++14
110 / 110
 1028 ms 109476 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N = 1e6+5;
int spf[N] , isprime[N];
set<int> primes[N];
bool on[N];
struct segTree{
    int n;
    vector<int> tree;
    bool b;
    int fun(int x,int y){
        return b ? max(x,y) : min(x,y);
    }
    segTree(int _n, bool _b){
        n = _n , b = _b;
        tree.resize(4*n+5,(b ? 0 : 1e9));
    }
    void update(int node,int l,int r,int idx,int val){
        if(l == r) return tree[node] = fun(tree[node] , val) , void();
        int md = l + r >> 1;
        idx <= md ? update(node<<1,l,md,idx,val) : update(node<<1|1,md+1,r,idx,val);
        tree[node] = fun(tree[node<<1],tree[node<<1|1]);
    }
    void set(int node,int l,int r,int idx,int val){
        if(l == r) return tree[node] = val , void();
        int md = l + r >> 1;
        idx <= md ? set(node<<1,l,md,idx,val) : set(node<<1|1,md+1,r,idx,val);
        tree[node] = fun(tree[node<<1],tree[node<<1|1]);
    }
    int query(int node,int l,int r,int lQ,int rQ){
        if(l > r || lQ > r || l > rQ) return (b ? 0 : 1e9);
        if(lQ <= l && r <= rQ) return tree[node];
        int md = l + r >> 1;
        return fun(query(node<<1,l,md,lQ,rQ) , query(node<<1|1,md+1,r,lQ,rQ));
    }
    void update(int idx,int x){
        update(1,1,n,idx,x);
    }
    void set(int idx,int x){
        set(1,1,n,idx,x);
    }
    int query(int l,int r){
        return query(1,1,n,l,r);
    }
};
vector<int> pFactors(int x){
    vector<int> tmp;
    int y = x;
    while(y != 1){
        if(tmp.empty() || tmp.back() != spf[y]) tmp.push_back(spf[y]);
        y /= spf[y];
    }
    return tmp;
}
segTree nxt(1e6,0);
segTree bef(1e6,1);
void calc(int x,bool b){
    vector<int> tmp = pFactors(x);
    for(auto p : tmp){
        if(!b) primes[p].erase(x);
        auto it = primes[p].lower_bound(x);
        if(it != primes[p].end()){
            if(b) bef.update(*it,x);
            nxt.update(x,*it);
        }
        if(it != primes[p].begin()){
            it --;
            if(b) nxt.update(*it,x);
            bef.update(x,*it);
        }
        primes[p].insert(x);
    }
}
void solve(){
    int n,q;
    cin>>n>>q;
    while(q--){
        char c;
        cin>>c;
        if(c == 'S'){
            int x;
            cin>>x;
            if(!on[x]){
                calc(x,1);
                on[x] = 1;
            }
            else {
                on[x] = 0;
                nxt.set(x,1e9);
                bef.set(x,0);
                vector<int> effected;
                vector<int> tmp = pFactors(x);
                for(auto p : tmp){
                    primes[p].erase(x);
                    auto it = primes[p].lower_bound(x);
                    if(it != primes[p].end()) effected.push_back(*it);
                    if(it != primes[p].begin()) effected.push_back(*(--it));
                }
                for(auto y : effected) nxt.set(y,1e9) , bef.set(y,0) , calc(y,0);
            }
        }
        else {
            int l,r;
            cin>>l>>r;
            int mxbef = bef.query(l,r);
            int mnnxt = nxt.query(l,r);
            cout<<(mxbef >= l || mnnxt <= r ? "DA" : "NE")<<endl;   
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    memset(isprime,1,sizeof(isprime));
    isprime[1] = 0;
    for(ll i=2;i<N;i++){
        if(!isprime[i]) continue;
        spf[i] = i;
        for(ll j=i*i;j<N;j+=i){
            if(!isprime[j]) continue;
            spf[j] = i;
            isprime[j] = 0;
        }
    }
    while(t--){
        solve();
    }
    return 0;
}

Compilation message

Main.cpp: In member function 'void segTree::update(int, int, int, int, int)':
Main.cpp:22:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         int md = l + r >> 1;
      |                  ~~^~~
Main.cpp: In member function 'void segTree::set(int, int, int, int, int)':
Main.cpp:28:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |         int md = l + r >> 1;
      |                  ~~^~~
Main.cpp: In member function 'int segTree::query(int, int, int, int, int)':
Main.cpp:35:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         int md = l + r >> 1;
      |                  ~~^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 87112 KB Output is correct
2 Correct 28 ms 87544 KB Output is correct
3 Correct 25 ms 87384 KB Output is correct
4 Correct 25 ms 87388 KB Output is correct
5 Correct 26 ms 87388 KB Output is correct
6 Correct 22 ms 87384 KB Output is correct
7 Correct 22 ms 87384 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 557 ms 93156 KB Output is correct
2 Correct 777 ms 103084 KB Output is correct
3 Correct 777 ms 106824 KB Output is correct
4 Correct 29 ms 87608 KB Output is correct
5 Correct 53 ms 88200 KB Output is correct
6 Correct 110 ms 88820 KB Output is correct

Subtask #3
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 87112 KB Output is correct
2 Correct 28 ms 87544 KB Output is correct
3 Correct 25 ms 87384 KB Output is correct
4 Correct 25 ms 87388 KB Output is correct
5 Correct 26 ms 87388 KB Output is correct
6 Correct 22 ms 87384 KB Output is correct
7 Correct 22 ms 87384 KB Output is correct
8 Correct 557 ms 93156 KB Output is correct
9 Correct 777 ms 103084 KB Output is correct
10 Correct 777 ms 106824 KB Output is correct
11 Correct 29 ms 87608 KB Output is correct
12 Correct 53 ms 88200 KB Output is correct
13 Correct 110 ms 88820 KB Output is correct
14 Correct 637 ms 88904 KB Output is correct
15 Correct 964 ms 92404 KB Output is correct
16 Correct 1028 ms 109476 KB Output is correct
17 Correct 799 ms 106072 KB Output is correct
18 Correct 915 ms 108008 KB Output is correct
19 Correct 890 ms 107748 KB Output is correct
20 Correct 102 ms 88916 KB Output is correct
21 Correct 96 ms 88920 KB Output is correct
22 Correct 107 ms 88980 KB Output is correct
23 Correct 119 ms 88984 KB Output is correct