oj.uz

Submission #1003537

# Submission time Handle Problem Language Result Execution time Memory
1003537 2024-06-20T12:35:08 Z Nailuj_217 Radio (COCI22_radio) C++17
0 / 110
 404 ms 34900 KB 
#include <bits/stdc++.h>
#define l long long
using namespace std;

const l LEN = 1000005;

array<pair<l, bool>, LEN*4+5> tree; 

bitset<LEN> sending;

pair<l, bool> insert_station(l i, l s, l f, l k) {
    if (k < s || k > f) return tree[i];
    if (s == f) return tree[i] = {s, false};

    pair<l, bool> left, right;
    left = insert_station(i*2, s, (s+f)/2, k);
    if (!left.first) left.first = 1;
    right = insert_station(i*2+1, (s+f)/2+1, f, k);
    if (!right.first) right.first = 1;


    if (left.second || right.second) return tree[i] = {lcm(left.first, right.first), true};
    else return tree[i] = {lcm(left.first, right.first), gcd(left.first, right.first) != 1};
}

pair<l, bool> erase_station(l i, l s, l f, l k) {
    if (k < s || k > f) return tree[i];
    if (s == f) return tree[i] = {1, false};

    pair<l, bool> left, right;
    left = erase_station(i*2, s, (s+f)/2, k);
    if (!left.first) left.first = 1;
    right = erase_station(i*2+1, (s+f)/2+1, f, k);
    if (!right.first) right.first = 1;


    if (left.second || right.second) return tree[i] = {lcm(left.first, right.first), true};
    else return tree[i] = {lcm(left.first, right.first), gcd(left.first, right.first) != 1};
}

pair<l, bool> query_range(l i, l s, l f, l a, l b) {
    if (a > f || b < s) return {0, false};
    if (a <= s && b >= f) return tree[i];
    pair<l, bool> left, right;
    left = query_range(i*2, s, (s+f)/2, a, b);
    if (!left.first) left.first = 1;
    right = query_range(i*2+1, (s+f)/2+1, f, a, b);
    if (!right.first) right.first = 1;

    if (left.second || right.second) return tree[i] = {lcm(left.first, right.first), true};
    else return tree[i] = {lcm(left.first, right.first), gcd(left.first, right.first) != 1};
}



int main() {



    l n, q;


    cin >> n >> q;
    

    string s;
    l a, b;
    


    while (q--) {

        cin >> s;
        if (s == "S") {
            cin >> a;
            if (sending[a]) {
                erase_station(1, 1, n, a);
                sending[a] = false;
            } else {
                insert_station(1, 1, n, a);
                sending[a] = true;
            }
        } else {
            cin >> a >> b;
            if (query_range(1, 1, n, a, b).second) cout << "DA" << endl;
            else cout << "NE" << endl;
        }


        b = a;

    }





    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 5460 KB Output is correct
2 Correct 364 ms 18300 KB Output is correct
3 Correct 404 ms 34900 KB Output is correct
4 Incorrect 27 ms 4700 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -