oj.uz

답안 #673509

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
673509 2022-12-20T19:24:14 Z Victor Radio (COCI22_radio) C++17
0 / 110
 1500 ms 281468 KB 
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define debug(x) cout<<#x<<" = "<<x<<endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;


struct Node {
    int lo,hi,val=INF;
    Node *l,*r;
    Node(int L,int R) : lo(L),hi(R) {
        if(hi-lo!=1) {
            int mid=(lo+hi)/2;
            l=new Node(lo,mid);
            r=new Node(mid,hi);
        }
    }

    int query(int L,int R) {
        if(hi<=L||R<=lo) return INF;
        if(L<=lo&&hi<=R) return val;
        return min(l->query(L,R),r->query(L,R));
    }

    void update(int pos,int x) {
        if(pos<lo||hi<=pos) return;
        if(hi-lo==1) {
            val=x;
            return;
        }

        l->update(pos,x);
        r->update(pos,x);
        val=min(l->val,r->val);
    }
};

const int MAXN = 1'000'000;
int n,q;
umap<int,set<int>> active_factors;
vi factors[MAXN+1];
set<int> neighbors[MAXN+1];
bitset<MAXN+1> active;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    rep(i,2,MAXN+1) if(factors[i].empty()) for(int j=i;j<=MAXN;j+=i) factors[j].pb(i);
    rep(i,1,MAXN+1) neighbors[i].insert(INF);
    
    cin>>n>>q;
    Node segtree(0,n);
    while(q--) {
        string op;
        cin>>op;
        if(op=="S") {
            int x;
            cin>>x;
            if(active[x]) {
                trav(factor,factors[x]) {
                    active_factors[factor].erase(x);
                    auto it=active_factors[factor].lower_bound(x);
                    int lnum=-1,rnum=-1;

                    if(it!=active_factors[factor].end()) rnum=*it;
                
                    if(it!=active_factors[factor].begin()) {
                        --it;
                        lnum=*it;
                        ++it;
                    }

                    if(lnum!=-1) neighbors[lnum].erase(x);
                    
                    //if(rnum!=-1) neighbors[x].insert(rnum);

                    if(lnum!=-1&&rnum!=-1) {
                        neighbors[lnum].insert(rnum);
                        segtree.update(lnum,*neighbors[lnum].begin());
                    }
                }

                segtree.update(x,INF);
                neighbors[x].clear();
                neighbors[x].insert(INF);

            } else {
                trav(factor,factors[x]) {
                    active_factors[factor].insert(x);
                    auto it=active_factors[factor].find(x);
                    int lnum=-1,rnum=-1;
                    if(it!=active_factors[factor].begin()) {
                        --it;
                        lnum=*it;
                        ++it;
                    }
                    ++it;
                    if(it!=active_factors[factor].end()) rnum=*it;
                    --it;

                    if(lnum!=-1&&rnum!=-1) neighbors[lnum].erase(rnum);

                    if(lnum!=-1) {
                        neighbors[lnum].insert(x);
                        segtree.update(lnum,*neighbors[lnum].begin());
                    }

                    if(rnum!=-1) neighbors[x].insert(rnum);
                }
                segtree.update(x,*neighbors[x].begin());
            }
            active[x]=!active[x];

        } else {
            int lo,hi;
            cin>>lo>>hi;
            ++hi;
            if(segtree.query(lo,hi)<hi) cout<<"DA"<<'\n';
            else cout<<"NE"<<'\n';
        }
    }
    //cout<<endl;
    //_Exit(0);
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1054 ms 171760 KB Output is correct
2 Correct 1449 ms 227952 KB Output is correct
3 Execution timed out 1605 ms 281468 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

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