oj.uz

Submission #542499

# Submission time Handle Problem Language Result Execution time Memory
542499 2022-03-26T19:13:55 Z Zhora_004 Radio (COCI22_radio) C++17
40 / 110
 1072 ms 136684 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <string>
#include <sstream>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <stack>
#include <cstdio>
#include <climits>
#include <tuple>
#include <ctime>
#include <cstring>
#include <numeric>
#include <functional>
#include <chrono>
#include <cassert>
#include <bitset>
//#include <bit>
//#include <ranges>
//#include <numbers>
#define itn int
#define sacnf scanf
#define sz(a) ((int)((a).size()))
// printf("%.10f\n", ans);
using ll = long long;
using namespace std;
const ll mod = 1e9 + 7;
const int N = 1e6 + 1, inf = 1e9;

void modify(vector<int>& segtree, int id, int v, int u, int tl, int tr)
{
    if (tl == tr) segtree[u] = v;
    else
    {
        int tm = (tl + tr) >> 1;
        if (id <= tm) modify(segtree, id, v, u * 2 + 1, tl, tm);
        else modify(segtree, id, v, u * 2 + 2, tm + 1, tr);
        segtree[u] = min(segtree[u * 2 + 1], segtree[u * 2 + 2]);
    }
}

int find_val(vector<int>& segtree, int& l, int& r, int u, int tl, int tr)
{
    if (tl > r || tr < l) return inf;
    if (l <= tl && tr <= r) return segtree[u];
    int tm = (tl + tr) >> 1;
    return min(find_val(segtree, l, r, u * 2 + 1, tl, tm), find_val(segtree, l, r, u * 2 + 2, tm + 1, tr));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    vector<set<int>> id(n + 1);
    vector<vector<int>> divs(n + 1);
    for (int i = 2; i <= n; i++) if (divs[i].empty()) for (int j = i; j <= n; j += i) divs[j].push_back(i);
    vector<int> L(n + 1, -1), R(n + 1, inf);
    vector<bool> on(n + 1);
    int len = 1;
    while (len <= n) len <<= 1;
    vector<int> segtree(len << 1, inf);
    while (q--)
    {
        char smb;
        cin >> smb;
        if (smb == 'S')
        {
            int x;
            cin >> x;
            if (on[x])
            {
                for (int& d : divs[x])
                {
                    set<int>& s = id[d];
                    s.erase(x);
                    auto it = s.upper_bound(x);
                    int l = -1, r = inf;
                    if (it != s.end()) r = *it;
                    if (it != s.begin()) l = *prev(it);
                    if (it != s.end())
                    {
                        int id1 = *it;
                        if (L[id1] == x) L[id1] = -1;
                        L[id1] = max(L[id1], l);
                    }
                    if (it != s.begin())
                    {
                        it--;
                        int id1 = *it;
                        if (R[id1] == x) R[id1] = inf;
                        R[id1] = min(R[id1], r);
                        modify(segtree, id1, R[id1], 0, 0, len - 1);
                    }
                }
                L[x] = -1;
                R[x] = inf;
                modify(segtree, x, R[x], 0, 0, len - 1);
            }
            else
            {
                for (int& d : divs[x])
                {
                    set<int>& s = id[d];
                    auto it = s.upper_bound(x);
                    if (it == s.end()) R[x] = min(R[x], inf);
                    else R[x] = min(R[x], *it), L[*it] = max(L[*it], x);
                    modify(segtree, x, R[x], 0, 0, len - 1);
                    if (it == s.begin()) L[x] = max(L[x], -1);
                    else it--, L[x] = max(L[x], *it), R[*it] = min(R[*it], x);
                    modify(segtree, *it, R[*it], 0, 0, len - 1);
                    s.insert(x);
                }
            }
            on[x] = !on[x];
        }
        else
        {
            int l, r;
            cin >> l >> r;
            int mn = find_val(segtree, l, r, 0, 0, len - 1);
            if (mn <= r) cout << "DA\n";
            else cout << "NE\n";
        }
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 17944 KB Output is correct
2 Correct 788 ms 74216 KB Output is correct
3 Correct 1072 ms 136684 KB Output is correct
4 Correct 25 ms 12244 KB Output is correct
5 Correct 228 ms 59464 KB Output is correct
6 Correct 475 ms 118948 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 354 ms 17944 KB Output is correct
9 Correct 788 ms 74216 KB Output is correct
10 Correct 1072 ms 136684 KB Output is correct
11 Correct 25 ms 12244 KB Output is correct
12 Correct 228 ms 59464 KB Output is correct
13 Correct 475 ms 118948 KB Output is correct
14 Incorrect 177 ms 676 KB Output isn't correct
15 Halted 0 ms 0 KB -