oj.uz

Submission #540839

# Submission time Handle Problem Language Result Execution time Memory
540839 2022-03-21T20:28:11 Z N1NT3NDO Radio (COCI22_radio) C++14
110 / 110
 1299 ms 198052 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 * 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(auto i : {2, 3, 5, 7, 11, 13, 17, 19})
    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;

            /*
            for(int i = 1; i <= n; i++)
            {
                if (sz(all[i]) > 0)
                {
                    cout << "! " << i << endl;
                    for(auto u : all[i]) cout << u << ' ';
                    cout << '\n';
                }

            }
            */

            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 53 ms 117708 KB Output is correct
2 Correct 57 ms 117736 KB Output is correct
3 Correct 55 ms 117740 KB Output is correct
4 Correct 53 ms 117716 KB Output is correct
5 Correct 60 ms 117728 KB Output is correct
6 Correct 54 ms 117648 KB Output is correct
7 Correct 60 ms 117628 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 542 ms 132964 KB Output is correct
2 Correct 983 ms 166720 KB Output is correct
3 Correct 1299 ms 193372 KB Output is correct
4 Correct 82 ms 121992 KB Output is correct
5 Correct 238 ms 138268 KB Output is correct
6 Correct 456 ms 158828 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 117708 KB Output is correct
2 Correct 57 ms 117736 KB Output is correct
3 Correct 55 ms 117740 KB Output is correct
4 Correct 53 ms 117716 KB Output is correct
5 Correct 60 ms 117728 KB Output is correct
6 Correct 54 ms 117648 KB Output is correct
7 Correct 60 ms 117628 KB Output is correct
8 Correct 542 ms 132964 KB Output is correct
9 Correct 983 ms 166720 KB Output is correct
10 Correct 1299 ms 193372 KB Output is correct
11 Correct 82 ms 121992 KB Output is correct
12 Correct 238 ms 138268 KB Output is correct
13 Correct 456 ms 158828 KB Output is correct
14 Correct 280 ms 118080 KB Output is correct
15 Correct 572 ms 125848 KB Output is correct
16 Correct 1284 ms 198052 KB Output is correct
17 Correct 1083 ms 190584 KB Output is correct
18 Correct 1199 ms 194548 KB Output is correct
19 Correct 1196 ms 194444 KB Output is correct
20 Correct 454 ms 158888 KB Output is correct
21 Correct 466 ms 158960 KB Output is correct
22 Correct 472 ms 159016 KB Output is correct
23 Correct 470 ms 158960 KB Output is correct