oj.uz

Submission #542503

# Submission time Handle Problem Language Result Execution time Memory
542503 2022-03-26T19:20:49 Z Zhora_004 Radio (COCI22_radio) C++17
40 / 110
 1026 ms 136744 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 0 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 0 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 291 ms 17912 KB Output is correct
2 Correct 733 ms 74224 KB Output is correct
3 Correct 1026 ms 136744 KB Output is correct
4 Correct 30 ms 12308 KB Output is correct
5 Correct 211 ms 59568 KB Output is correct
6 Correct 442 ms 118868 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 0 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 0 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 291 ms 17912 KB Output is correct
9 Correct 733 ms 74224 KB Output is correct
10 Correct 1026 ms 136744 KB Output is correct
11 Correct 30 ms 12308 KB Output is correct
12 Correct 211 ms 59568 KB Output is correct
13 Correct 442 ms 118868 KB Output is correct
14 Incorrect 216 ms 688 KB Output isn't correct
15 Halted 0 ms 0 KB -