oj.uz

Submission #540845

# Submission time Handle Problem Language Result Execution time Memory
540845 2022-03-21T20:34:25 Z N1NT3NDO Radio (COCI22_radio) C++14
110 / 110
 1295 ms 198184 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

using namespace std;
//using namespace __gnu_pbds;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = (int)1e6 + 5;
int n, q, cnt, skok[N], t[4 * N];
bool was[N];
vector< int > del[N];
set < int > se[N];
multiset< int > all[N];

void build(int v, int tl, int tr)
{
    t[v] = 1e9;
    if (tl == tr) return;
    int m = (tl + tr) >> 1;
    build(v + v, tl, m);
    build(v + v + 1, m + 1, tr);
}

void upd(int v, int tl, int tr, int pos, int val)
{
    if (tl == tr)
    {
        t[v] = val;
        return;
    }

    int m = (tl + tr) >> 1;

    if (pos <= m)
      upd(v + v, tl, m, pos, val);
    else upd(v + v + 1, m + 1, tr, pos, val);
    t[v] = min(t[v + v], t[v + v + 1]);
}

int get(int v, int tl, int tr, int l, int r)
{
    if (tl > tr || tl > r || tr < l) return 1e9;

    if (tl >= l && tr <= r) return t[v];

    int m = (tl + tr) >> 1;

    return min(get(v + v, tl, m, l, r), get(v + v + 1, m + 1, tr, l, r));
}

void upd(int x)
{
    if (!x) return;

    int val = 1e9;

    if (sz(all[x]) > 0) val = *all[x].begin();

    upd(1, 1, n, x, val);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;

    for(int i = 2; i <= n; i++)
    {
        if (sz(del[i])) continue;

        for(int j = i; j <= n; j += i)
            del[j].pb(i);
    }

    build(1, 1, n);

    while(q--)
    {
        char c;
        cin >> c;
        if (c == 'S')
        {
            int x;
            cin >> x;
            if (was[x])
            {
                for(auto d : del[x])
                {
                    auto it = se[d].lower_bound(x);
                    int r = 0, l = 0;
                    if (next(it) != se[d].end()) r = *next(it);
                    if (it != se[d].begin()) l = *prev(it);
                    if (l) all[l].erase(all[l].find(x));
                    if (r) all[x].erase(all[x].find(r));
                    if (l && r) all[l].insert(r);
                    upd(l); upd(x);
                    se[d].erase(x);
                }
            }
            else
            {
                for(auto d : del[x])
                {
                    auto it = se[d].upper_bound(x);
                    int r = 0, l = 0;
                    if (it != se[d].end()) r = *it;
                    if (it != se[d].begin()) l = *prev(it);
                    if (l) all[l].insert(x);
                    if (r) all[x].insert(r);
                    if (l && r) all[l].erase(all[l].find(r));
                    upd(l); upd(x);
                    se[d].insert(x);
                }
            }

            was[x] ^= 1;
        }
        else
        {
            int l, r;
            cin >> l >> r;

            if (get(1, 1, n, l, r) <= r) cout << "DA" << '\n';
            else cout << "NE" << '\n';
        }
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 117664 KB Output is correct
2 Correct 51 ms 117628 KB Output is correct
3 Correct 53 ms 117716 KB Output is correct
4 Correct 52 ms 117656 KB Output is correct
5 Correct 52 ms 117744 KB Output is correct
6 Correct 51 ms 117704 KB Output is correct
7 Correct 51 ms 117704 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 132920 KB Output is correct
2 Correct 872 ms 166716 KB Output is correct
3 Correct 1133 ms 193356 KB Output is correct
4 Correct 88 ms 121928 KB Output is correct
5 Correct 247 ms 138368 KB Output is correct
6 Correct 444 ms 158952 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 117664 KB Output is correct
2 Correct 51 ms 117628 KB Output is correct
3 Correct 53 ms 117716 KB Output is correct
4 Correct 52 ms 117656 KB Output is correct
5 Correct 52 ms 117744 KB Output is correct
6 Correct 51 ms 117704 KB Output is correct
7 Correct 51 ms 117704 KB Output is correct
8 Correct 468 ms 132920 KB Output is correct
9 Correct 872 ms 166716 KB Output is correct
10 Correct 1133 ms 193356 KB Output is correct
11 Correct 88 ms 121928 KB Output is correct
12 Correct 247 ms 138368 KB Output is correct
13 Correct 444 ms 158952 KB Output is correct
14 Correct 264 ms 118088 KB Output is correct
15 Correct 605 ms 125880 KB Output is correct
16 Correct 1295 ms 198184 KB Output is correct
17 Correct 1107 ms 190644 KB Output is correct
18 Correct 1158 ms 194512 KB Output is correct
19 Correct 1188 ms 194364 KB Output is correct
20 Correct 455 ms 158948 KB Output is correct
21 Correct 462 ms 158992 KB Output is correct
22 Correct 465 ms 159000 KB Output is correct
23 Correct 472 ms 158964 KB Output is correct