제출 #1156329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156329		AHOKA	Radio (COCI22_radio)	C++20	10 / 110	1609 ms	311684 KiB

Main

#pragma GCC optimize("O3") 
#pragma GCC target("sse4")

#include <bits/stdc++.h>

using namespace std;
 
#define threesum cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
#define all(a) a.begin(), a.end()
#define F first
#define S second
#define int long long
#define pii pair<int, int>
#define ppp pair<int, pii>
#define dout cout << fixed << setprecision(15)
#define mid ((l + r) / 2)
#define lc (2 * id)
#define rc (lc + 1)

const int maxn = 1e6 + 10, maxm = 7e2 + 10, oo = 1e18 + 10, lg = 33, sq = 350, mod = 998244353;

int n, m;
set<int> a[2][maxn];

vector<int> p[maxn];
set<int> ind[maxn];

int mn[maxn << 2], mx[maxn << 2];

void sieve(){
    for (int i = 2; i < maxn;i++)
        if(!p[i].size())
            for (int j = i; j < maxn; j += i)
                p[j].push_back(i);
}

void merge(int id){
    mx[id] = max(mx[lc], mx[rc]);
    mn[id] = min(mn[lc], mn[rc]);
}

void build(int id = 1, int l = 0, int r = maxn){
    if (r - l == 1)
    {
        mn[id] = oo;
        mx[id] = -oo;
        return;
    }

    build(lc, l, mid);
    build(rc, mid, r);

    merge(id);
}

void updmx(int i, int v, int id = 1, int l = 0, int r = maxn){
    if(r - l == 1){
        a[0][l].insert(v);
        mx[id] = *a[0][l].rbegin();
        return;
    }

    if(i < mid)
        updmx(i, v, lc, l, mid);
    else 
        updmx(i, v, rc, mid, r);

    merge(id);
}

void updmn(int i, int v, int id = 1, int l = 0, int r = maxn){
    if(r - l == 1){
        a[1][l].insert(v);
        mn[id] = *a[1][l].begin();
        return;
    }

    if(i < mid)
        updmn(i, v, lc, l, mid);
    else 
        updmn(i, v, rc, mid, r);

    merge(id);
}

int getmx(int ql, int qr, int id = 1, int l = 0, int r = maxn){
    if(r <= ql || qr <= l)
        return -oo;
    
    if(ql <= l && r <= qr)
        return mx[id];

    return max(getmx(ql, qr, lc, l, mid), getmx(ql, qr, rc, mid, r));
}

int getmn(int ql, int qr, int id = 1, int l = 0, int r = maxn){
    if(r <= ql || qr <= l)
        return oo;
    
    if(ql <= l && r <= qr)
        return mn[id];

    return min(getmn(ql, qr, lc, l, mid), getmn(ql, qr, rc, mid, r));
}

void upd(int x){
    bool f = 0;

    for (auto i : p[x])
    {
        auto it = ind[i].lower_bound(x);

        if(it != ind[i].end()){
            if(*it == x){
                f = 1;

                if (it != ind[i].begin())
                {
                    auto prv = it;
                    prv--;

                    a[1][*prv].erase(x);
                    updmn(*prv, oo);
                }

                auto nxt = it;
                nxt++;

                if(nxt != ind[i].end()){
                    a[0][*nxt].erase(x);
                    updmx(*nxt, -oo);
                }

                ind[i].erase(x);
            }
            else{
                if(it != ind[i].begin()){
                    auto prv = it;
                    prv--;

                    updmn(*prv, x);
                    updmx(x, *prv);
                }

                updmn(x, *it);
                updmx(*it, x);

                ind[i].insert(x);
            }
        }
        else{
            if(it != ind[i].begin()){
                auto prv = it;
                prv--;

                updmn(*prv, x);
                updmx(x, *prv);
            }

            ind[i].insert(x);
        }
    }

    if(f){
        a[0][x].clear();
        a[1][x].clear();
        updmn(x, oo);
        updmx(x, -oo);
    }
}

signed main()
{
    threesum;

    sieve();

    cin >> n >> m;

    build();

    while(m--){
        char c;
        cin >> c;
        if(c == 'S'){
            int x;
            cin >> x;
            upd(x);
        }
        else{
            int l, r;
            cin >> l >> r;
            r++;
            
            if(getmn(l, r) < r || l <= getmx(l, r))
                cout << "DA\n";
            else
                cout << "NE\n";
        }
    }
}
/*
6 6
S 3
S 6
C 3 6
S 3
S 6
C 3 6
*/

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