oj.uz

Submission #542046

# Submission time Handle Problem Language Result Execution time Memory
542046 2022-03-25T08:50:40 Z kamilszymczak11 Radio (COCI22_radio) C++17
110 / 110
 1006 ms 145712 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 340 KB Output is correct
6 Correct 0 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 389 ms 22084 KB Output is correct
2 Correct 707 ms 81984 KB Output is correct
3 Correct 832 ms 140876 KB Output is correct
4 Correct 12 ms 11092 KB Output is correct
5 Correct 68 ms 53388 KB Output is correct
6 Correct 144 ms 106524 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 389 ms 22084 KB Output is correct
9 Correct 707 ms 81984 KB Output is correct
10 Correct 832 ms 140876 KB Output is correct
11 Correct 12 ms 11092 KB Output is correct
12 Correct 68 ms 53388 KB Output is correct
13 Correct 144 ms 106524 KB Output is correct
14 Correct 181 ms 744 KB Output is correct
15 Correct 537 ms 11720 KB Output is correct
16 Correct 1006 ms 145712 KB Output is correct
17 Correct 853 ms 138160 KB Output is correct
18 Correct 884 ms 142040 KB Output is correct
19 Correct 879 ms 141988 KB Output is correct
20 Correct 148 ms 106444 KB Output is correct
21 Correct 149 ms 106520 KB Output is correct
22 Correct 131 ms 106432 KB Output is correct
23 Correct 166 ms 106512 KB Output is correct