oj.uz

Submission #545753

# Submission time Handle Problem Language Result Execution time Memory
545753 2022-04-05T11:33:20 Z mat50013 Radio (COCI22_radio) C++11
110 / 110
 1191 ms 129560 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(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);
    }
};

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

    SegTree Seg(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;
                int bz = care;
                while(care != 1)
                {
                    int div = lp[care];
                    while(care % div == 0)
                        care /= div;
                    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, 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);
                }
                care = bz;
                Seg.update(1, 1, n, bz, 0);
                while(care != 1)
                {
                    int div = lp[care];
                    while(care % div == 0)
                        care /= div;
                    auto ce = vals[div].lower_bound(bz);
                    if(ce != vals[div].begin()){
                        --ce;
                        Seg.update(1, 1, n, *ce, 1);
                    }
                }
            }
        }
        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 47316 KB Output is correct
2 Correct 23 ms 47188 KB Output is correct
3 Correct 23 ms 47312 KB Output is correct
4 Correct 24 ms 47304 KB Output is correct
5 Correct 22 ms 47316 KB Output is correct
6 Correct 22 ms 47316 KB Output is correct
7 Correct 23 ms 47340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 59136 KB Output is correct
2 Correct 834 ms 92136 KB Output is correct
3 Correct 993 ms 125440 KB Output is correct
4 Correct 36 ms 53704 KB Output is correct
5 Correct 106 ms 77520 KB Output is correct
6 Correct 218 ms 108968 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47316 KB Output is correct
2 Correct 23 ms 47188 KB Output is correct
3 Correct 23 ms 47312 KB Output is correct
4 Correct 24 ms 47304 KB Output is correct
5 Correct 22 ms 47316 KB Output is correct
6 Correct 22 ms 47316 KB Output is correct
7 Correct 23 ms 47340 KB Output is correct
8 Correct 493 ms 59136 KB Output is correct
9 Correct 834 ms 92136 KB Output is correct
10 Correct 993 ms 125440 KB Output is correct
11 Correct 36 ms 53704 KB Output is correct
12 Correct 106 ms 77520 KB Output is correct
13 Correct 218 ms 108968 KB Output is correct
14 Correct 248 ms 48824 KB Output is correct
15 Correct 520 ms 54792 KB Output is correct
16 Correct 1191 ms 129560 KB Output is correct
17 Correct 950 ms 126196 KB Output is correct
18 Correct 1060 ms 127564 KB Output is correct
19 Correct 1050 ms 127980 KB Output is correct
20 Correct 185 ms 109268 KB Output is correct
21 Correct 187 ms 109052 KB Output is correct
22 Correct 206 ms 108888 KB Output is correct
23 Correct 214 ms 109124 KB Output is correct