oj.uz

Submission #542497

# Submission time Handle Problem Language Result Execution time Memory
542497 2022-03-26T19:11:02 Z Zhora_004 Radio (COCI22_radio) C++17
40 / 110
 1008 ms 136788 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 0 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 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 17884 KB Output is correct
2 Correct 737 ms 74260 KB Output is correct
3 Correct 1008 ms 136788 KB Output is correct
4 Correct 29 ms 12244 KB Output is correct
5 Correct 220 ms 59580 KB Output is correct
6 Correct 453 ms 118844 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 328 ms 17884 KB Output is correct
9 Correct 737 ms 74260 KB Output is correct
10 Correct 1008 ms 136788 KB Output is correct
11 Correct 29 ms 12244 KB Output is correct
12 Correct 220 ms 59580 KB Output is correct
13 Correct 453 ms 118844 KB Output is correct
14 Incorrect 188 ms 724 KB Output isn't correct
15 Halted 0 ms 0 KB -