oj.uz

Submission #545766

# Submission time Handle Problem Language Result Execution time Memory
545766 2022-04-05T11:53:03 Z mat50013 Radio (COCI22_radio) C++17
110 / 110
 1286 ms 127968 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 29 ms 47164 KB Output is correct
2 Correct 27 ms 47204 KB Output is correct
3 Correct 21 ms 47188 KB Output is correct
4 Correct 21 ms 47316 KB Output is correct
5 Correct 21 ms 47248 KB Output is correct
6 Correct 22 ms 47304 KB Output is correct
7 Correct 21 ms 47300 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 59252 KB Output is correct
2 Correct 906 ms 92076 KB Output is correct
3 Correct 979 ms 125620 KB Output is correct
4 Correct 37 ms 53588 KB Output is correct
5 Correct 98 ms 77616 KB Output is correct
6 Correct 218 ms 107888 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47164 KB Output is correct
2 Correct 27 ms 47204 KB Output is correct
3 Correct 21 ms 47188 KB Output is correct
4 Correct 21 ms 47316 KB Output is correct
5 Correct 21 ms 47248 KB Output is correct
6 Correct 22 ms 47304 KB Output is correct
7 Correct 21 ms 47300 KB Output is correct
8 Correct 444 ms 59252 KB Output is correct
9 Correct 906 ms 92076 KB Output is correct
10 Correct 979 ms 125620 KB Output is correct
11 Correct 37 ms 53588 KB Output is correct
12 Correct 98 ms 77616 KB Output is correct
13 Correct 218 ms 107888 KB Output is correct
14 Correct 301 ms 47532 KB Output is correct
15 Correct 540 ms 53520 KB Output is correct
16 Correct 1286 ms 127968 KB Output is correct
17 Correct 977 ms 124176 KB Output is correct
18 Correct 1094 ms 126152 KB Output is correct
19 Correct 1132 ms 126000 KB Output is correct
20 Correct 218 ms 107720 KB Output is correct
21 Correct 204 ms 107720 KB Output is correct
22 Correct 187 ms 107720 KB Output is correct
23 Correct 182 ms 107788 KB Output is correct