oj.uz

Submission #545764

# Submission time Handle Problem Language Result Execution time Memory
545764 2022-04-05T11:52:02 Z mat50013 Radio (COCI22_radio) C++11
110 / 110
 1252 ms 127984 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47232 KB Output is correct
2 Correct 22 ms 47220 KB Output is correct
3 Correct 25 ms 47188 KB Output is correct
4 Correct 28 ms 47188 KB Output is correct
5 Correct 28 ms 47192 KB Output is correct
6 Correct 27 ms 47292 KB Output is correct
7 Correct 21 ms 47308 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 59212 KB Output is correct
2 Correct 844 ms 92104 KB Output is correct
3 Correct 1014 ms 125456 KB Output is correct
4 Correct 36 ms 53588 KB Output is correct
5 Correct 95 ms 77540 KB Output is correct
6 Correct 181 ms 107896 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47232 KB Output is correct
2 Correct 22 ms 47220 KB Output is correct
3 Correct 25 ms 47188 KB Output is correct
4 Correct 28 ms 47188 KB Output is correct
5 Correct 28 ms 47192 KB Output is correct
6 Correct 27 ms 47292 KB Output is correct
7 Correct 21 ms 47308 KB Output is correct
8 Correct 388 ms 59212 KB Output is correct
9 Correct 844 ms 92104 KB Output is correct
10 Correct 1014 ms 125456 KB Output is correct
11 Correct 36 ms 53588 KB Output is correct
12 Correct 95 ms 77540 KB Output is correct
13 Correct 181 ms 107896 KB Output is correct
14 Correct 274 ms 47544 KB Output is correct
15 Correct 492 ms 53668 KB Output is correct
16 Correct 1252 ms 127984 KB Output is correct
17 Correct 884 ms 124304 KB Output is correct
18 Correct 1117 ms 126180 KB Output is correct
19 Correct 1027 ms 126008 KB Output is correct
20 Correct 208 ms 107792 KB Output is correct
21 Correct 178 ms 107680 KB Output is correct
22 Correct 178 ms 107720 KB Output is correct
23 Correct 180 ms 107796 KB Output is correct