Submission #545764

#	Time	Username	Problem	Language	Result	Execution time	Memory
545764		mat50013	Radio (COCI22_radio)	C++11	110 / 110	1252 ms	127984 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int NMAX(1000005);
int lp[NMAX], n, q;
bool activ[NMAX];
set<int> vals[NMAX];

struct SegTree
{
    vector<int> arb;
    SegTree(){}
    inline void init(int n)
    {
        int pt = 1;
        while(pt < n)
            pt <<= 1;
        pt <<= 1;
        arb.resize(pt, n + 1);
    }
    inline void update(int nod, int st, int dr, int poz, bool tip)
    {
        if(st == dr)
        {
            if(tip == 1)
            {
                int bz = poz;
                arb[nod] = n + 1;
                while(poz != 1)
                {
                    int div = lp[poz];
                    while(poz % div == 0)
                        poz /= div;
                    arb[nod] = min(arb[nod], *vals[div].upper_bound(bz));
                }
            }
            else
                arb[nod] = n + 1;
            return;
        }
        int mij = (st + dr) / 2;
        if(poz <= mij)
            update(2 * nod, st, mij, poz, tip);
        else update(2 * nod + 1, mij + 1, dr, poz, tip);
        arb[nod] = min(arb[2 * nod], arb[2 * nod + 1]);
    }
    inline int query(int nod, int st, int dr, int a, int b)
    {
        if(a <= st && dr <= b)
            return arb[nod];
        int mij = (st + dr) / 2;
        int rez1 = n + 1, rez2 = n + 1;
        if(a <= mij)
            rez1 = query(2 * nod, st, mij, a, b);
        if(b > mij)
            rez2 = query(2 * nod + 1, mij + 1, dr, a, b);
        return min(rez1, rez2);
    }
} Seg;

inline void modif(int care, int tip)
{
    int bz = care;
    while(care != 1)
    {
        int div = lp[care];
        while(care % div == 0)
            care /= div;
        if(tip == 1)
            vals[div].insert(bz);
        auto ce = vals[div].lower_bound(bz);
        if(ce != vals[div].begin())
        {
            --ce;
            Seg.update(1, 1, n, *ce, 1);
        }
    }
    Seg.update(1, 1, n, bz, tip);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> q;

    for(int i = 1; i <= n; ++i)
        vals[i].insert(n + 1);

    vector<int> prime;
    for(int i = 2; i <= n; ++i)
    {
        if(!lp[i])
        {
            lp[i] = i;
            prime.push_back(i);
        }
        for(int j = 0; j < (int)prime.size() && prime[j] <= lp[i] && i * prime[j] <= n; ++j)
            lp[i * prime[j]] = prime[j];
    }

    Seg.init(n);
    for(int i = 1; i <= q; ++i)
    {
        char tip;
        cin >> tip;

        if(tip == 'S')
        {
            int care;
            cin >> care;
            if(!activ[care])
            {
                activ[care] = 1;
                modif(care, 1);
            }
            else
            {
                activ[care] = 0;
                int bz = care;
                while(care != 1)
                {
                    int div = lp[care];
                    while(care % div == 0)
                        care /= div;
                    vals[div].erase(bz);
                }
                modif(bz, 0);
            }
        }
        else
        {
            int st, dr;
            cin >> st >> dr;
            cout << (Seg.query(1, 1, n, st, dr) <= dr ? "DA\n" : "NE\n");
        }
    }
    return 0;
}

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