oj.uz

Submission #540842

# Submission time Handle Problem Language Result Execution time Memory
540842 2022-03-21T20:30:08 Z N1NT3NDO Radio (COCI22_radio) C++17
110 / 110
 1300 ms 198220 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 + 3;
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 * 2, tl, m);
    build(v * 2 + 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 * 2, tl, m, pos, val);
    else upd(v * 2 + 1, m + 1, tr, pos, val);
    t[v] = min(t[v * 2], t[v * 2 + 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 * 2, tl, m, l, r), get(v * 2 + 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(const 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 51 ms 117708 KB Output is correct
2 Correct 53 ms 117700 KB Output is correct
3 Correct 51 ms 117744 KB Output is correct
4 Correct 51 ms 117736 KB Output is correct
5 Correct 56 ms 117648 KB Output is correct
6 Correct 51 ms 117708 KB Output is correct
7 Correct 52 ms 117640 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 132984 KB Output is correct
2 Correct 877 ms 166756 KB Output is correct
3 Correct 1121 ms 193472 KB Output is correct
4 Correct 73 ms 122020 KB Output is correct
5 Correct 234 ms 138352 KB Output is correct
6 Correct 477 ms 158952 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 117708 KB Output is correct
2 Correct 53 ms 117700 KB Output is correct
3 Correct 51 ms 117744 KB Output is correct
4 Correct 51 ms 117736 KB Output is correct
5 Correct 56 ms 117648 KB Output is correct
6 Correct 51 ms 117708 KB Output is correct
7 Correct 52 ms 117640 KB Output is correct
8 Correct 480 ms 132984 KB Output is correct
9 Correct 877 ms 166756 KB Output is correct
10 Correct 1121 ms 193472 KB Output is correct
11 Correct 73 ms 122020 KB Output is correct
12 Correct 234 ms 138352 KB Output is correct
13 Correct 477 ms 158952 KB Output is correct
14 Correct 268 ms 118148 KB Output is correct
15 Correct 579 ms 125908 KB Output is correct
16 Correct 1300 ms 198220 KB Output is correct
17 Correct 1137 ms 190600 KB Output is correct
18 Correct 1178 ms 194436 KB Output is correct
19 Correct 1191 ms 194448 KB Output is correct
20 Correct 470 ms 158872 KB Output is correct
21 Correct 454 ms 158972 KB Output is correct
22 Correct 461 ms 158960 KB Output is correct
23 Correct 499 ms 159112 KB Output is correct