Submission #1003537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003537		Nailuj_217	Radio (COCI22_radio)	C++17	0 / 110	404 ms	34900 KiB

Main

#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
• Subtask 2: 0 / 30
• Subtask 3: 0 / 70