Submission #1156364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156364		AHOKA	Radio (COCI22_radio)	C++20	40 / 110	815 ms	207380 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 = 1e9 + 10, lg = 33, sq = 350, mod = 998244353;

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

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

int 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]);
}

void build(int id = 1, int l = 1, int r = n + 1){
    if (r - l == 1)
    {
        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 = 1, int r = n + 1){
    if(r - l == 1){
        a[l].insert(v);
        mx[id] = *a[l].rbegin();
        return;
    }

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

    merge(id);
}

int getmx(int ql, int qr, int id = 1, int l = 1, int r = n + 1){
    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));
}

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;

                auto nxt = it;
                nxt++;

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

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

                updmx(*it, x);

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

                updmx(x, *prv);
            }

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

    if(f){
        a[x].clear();
        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(l <= getmx(l, r))
                cout << "DA\n";
            else
                cout << "NE\n";
        }
    }
}

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