oj.uz

Submission #540843

# Submission time Handle Problem Language Result Execution time Memory
540843 2022-03-21T20:30:36 Z N1NT3NDO Radio (COCI22_radio) C++17
110 / 110
 1331 ms 198240 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].emplace_back(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 62 ms 117736 KB Output is correct
2 Correct 55 ms 117628 KB Output is correct
3 Correct 61 ms 117652 KB Output is correct
4 Correct 66 ms 117688 KB Output is correct
5 Correct 56 ms 117664 KB Output is correct
6 Correct 52 ms 117672 KB Output is correct
7 Correct 54 ms 117756 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 132924 KB Output is correct
2 Correct 875 ms 166624 KB Output is correct
3 Correct 1174 ms 193300 KB Output is correct
4 Correct 74 ms 121924 KB Output is correct
5 Correct 246 ms 138276 KB Output is correct
6 Correct 466 ms 158948 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 117736 KB Output is correct
2 Correct 55 ms 117628 KB Output is correct
3 Correct 61 ms 117652 KB Output is correct
4 Correct 66 ms 117688 KB Output is correct
5 Correct 56 ms 117664 KB Output is correct
6 Correct 52 ms 117672 KB Output is correct
7 Correct 54 ms 117756 KB Output is correct
8 Correct 464 ms 132924 KB Output is correct
9 Correct 875 ms 166624 KB Output is correct
10 Correct 1174 ms 193300 KB Output is correct
11 Correct 74 ms 121924 KB Output is correct
12 Correct 246 ms 138276 KB Output is correct
13 Correct 466 ms 158948 KB Output is correct
14 Correct 264 ms 118100 KB Output is correct
15 Correct 568 ms 125820 KB Output is correct
16 Correct 1331 ms 198240 KB Output is correct
17 Correct 1079 ms 190500 KB Output is correct
18 Correct 1242 ms 194532 KB Output is correct
19 Correct 1197 ms 194444 KB Output is correct
20 Correct 459 ms 158940 KB Output is correct
21 Correct 458 ms 159064 KB Output is correct
22 Correct 463 ms 158960 KB Output is correct
23 Correct 462 ms 158968 KB Output is correct