Submission #542046

#	Time	Username	Problem	Language	Result	Execution time	Memory
542046		kamilszymczak11	Radio (COCI22_radio)	C++17	110 / 110	1006 ms	145712 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

const int inf = 1 << 25;

struct SegTree {
    vector<int>values;
    int leafCount;
    SegTree(int n) {
        for(leafCount = 1; leafCount < n; leafCount *= 2) {}
        values.resize(leafCount * 2, inf);
    }
    void Set(int x, int value) {
        x += leafCount;
        values[x] = value;
        for(x /= 2; x; x /= 2)
            values[x] = min(values[x * 2], values[x * 2 + 1]);
    }
    int GetMin(int a, int b) {
        a += leafCount; b += leafCount;
        int result = min(values[a], values[b]);
        for(; a / 2 != b / 2; a /= 2, b /= 2) {
            if(a % 2 == 0) result = min(result, values[a + 1]);
            if(b % 2 == 1) result = min(result, values[b - 1]);
        }
        return result;
    }
};

void SwitchOn(int x, vector<int>&primeFactors, vector<set<int>>&s, vector<multiset<int>>&following, SegTree &T) {
    //cout << "switch on\n" << flush;
    for(int f : primeFactors) {
        auto it = s[f].insert(x).first;
        auto prev = it;
        auto next = it; next++;
        if(it != s[f].begin())
            prev--;
        if(it != s[f].begin() && next != s[f].end()) {
            following[*prev].erase(following[*prev].find(*next));
            if(following[*prev].empty())
                T.Set(*prev, inf);
            else
                T.Set(*prev, *following[*prev].begin());
        }
        
        if(it != s[f].begin()) {
            following[*prev].insert(x);
            if(following[*prev].empty())
                T.Set(*prev, inf);
            else
                T.Set(*prev, *following[*prev].begin());
        }
        if(next != s[f].end()) {
            following[x].insert(*next);
        }
    }
    if(following[x].empty())
        T.Set(x, inf);
    else
        T.Set(x, *following[x].begin());
   // cout << "done\n" << flush;
}

void SwitchOff(int x, vector<int>&primeFactors, vector<set<int>>&s, vector<multiset<int>>&following, SegTree &T) {
    //cout << "switch off\n" << flush;
    for(int f : primeFactors) {
        auto it = s[f].find(x);
        auto prev = it;
        auto next = it; next++;
        if(it != s[f].begin())
            prev--;
        if(it != s[f].begin() && next != s[f].end()) {
            following[*prev].erase(following[*prev].find(x));
            following[*prev].insert(*next);
            T.Set(*prev, *following[*prev].begin());
        }
        
        if(it != s[f].begin() && next == s[f].end()) {
            following[*prev].erase(following[*prev].find(x));
            if(following[*prev].empty())
                T.Set(*prev, inf);
            else
                T.Set(*prev, *following[*prev].begin());
        }
        
        s[f].erase(it);
    }
    following[x].clear();
    T.Set(x, inf);
   // cout << "done\n" << flush;
}

int main() {
    ios_base::sync_with_stdio(0);
    int n, q; cin >> n >> q;
    
    vector<int>factor(n + 1, -1);
    for(int i = 2; i <= n; i++) {
        if(factor[i] == -1) {
            for(int j = i; j <= n; j += i)
                factor[j] = i;
        }
    }
    vector<set<int>>s(n + 1);
    vector<multiset<int>>next(n + 1);
    vector<bool>active(n + 1, false);
    SegTree T(n + 7);
    while(q--) {
        char c; cin >> c;
        if(c == 'S') {
            int x; cin >> x;
            if(x == 1) continue;
            vector<int>primeFactors;
            for(int y = x; y != 1; ) {
                primeFactors.push_back(factor[y]);
                int f = factor[y];
                while(y % f == 0) y /= f;
            }
            if(active[x]) {
                SwitchOff(x, primeFactors, s, next, T);
            } else {
                SwitchOn(x, primeFactors, s, next, T);
            }
            active[x] = !active[x];
        } else {
            int l, r; cin >> l >> r;
            int m = T.GetMin(l, r);
            if(m <= r) {
                cout << "DA\n";
            } else {
                cout << "NE\n";
            }
        }
    }
    
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70