oj.uz

Submission #543998

# Submission time Handle Problem Language Result Execution time Memory
543998 2022-03-31T19:19:55 Z Victor Radio (COCI22_radio) C++17
10 / 110
 1500 ms 316248 KB 
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

struct Node {
    Node *l, *r;
    int val, lo, hi;
    map<int, int> stops;

    Node(int L, int R) : lo(L), hi(R) {
        if (hi - lo == 1) {
            ++stops[INF];
            val = INF;

        } else {
            int mid = (lo + hi) / 2;
            l = new Node(lo, mid);
            r = new Node(mid, hi);
            val = min(l->val, r->val);
        }
    }

    int query(int L, int R) {
        if (hi <= L || R <= lo) return INF;
        if (L <= lo && hi <= R) return val;

        return min(l->query(L, R), r->query(L, R));
    }

    void update(int pos, int x, int y) {
        if (hi <= pos || pos < lo) return;
        if (hi - lo == 1) {
            stops[x] += y;
            if (!stops[x]) stops.erase(x);
            val = stops.begin()->first;
            return;
        }

        l->update(pos, x, y), r->update(pos, x, y);
        val = min(l->val, r->val);
    }
};

const int primes[168]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};

set<int> factors[1'000'005];
bitset<1'000'005> broadcast;
Node *segtree;
int n, q;

void toggle(int factor, int freq) {
    int mul = broadcast[freq] ? -1 : 1;

    if (broadcast[freq])
        factors[factor].erase(freq);
    else
        factors[factor].insert(freq);

    auto it = factors[factor].upper_bound(freq);

    // cout << "factor = " << factor << " freq = " << freq << " broadcast = " << broadcast[factor] << endl;

    int hi = -1, lo = -1;
    if (it != factors[factor].end()) {
        hi = *it;
        segtree->update(freq, hi, 1 * mul);
        //  cout<<"WA1"<<endl;
    }

    if (!broadcast[freq]) --it;
    if (it != factors[factor].begin()) {
        --it;
        lo = *it;
        segtree->update(lo, freq, 1 * mul);
        //  cout<<"WA2"<<endl;
    }

    if (lo != -1 && hi != -1) {
        segtree->update(lo, hi, -1 * mul);
        // cout << "WA3" << endl;
    }

}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    
    cin >> n >> q;
    segtree = new Node(0, n + 5);

    while (q--) {
        char type;
        cin >> type;

        if (type == 'S') {
            int freq;
            cin >> freq;

            int val = freq;
            rep(i,0,168) {
                if (primes[i] * primes[i] > val) break;

                if (val % primes[i] == 0) toggle(primes[i], freq);
                while (val % primes[i] == 0) val /= primes[i];
            }
            if (val != 1) toggle(val, freq);

            broadcast[freq] = !broadcast[freq];

        } else {
            int lo, hi;
            cin >> lo >> hi;

            int val = segtree->query(lo, hi + 1);
            //cout << "lo = " << lo << " hi = " << hi << " val = " << val << endl;

            if (val <= hi)
                cout << "DA" << '\n';
            else
                cout << "NE" << '\n';
        }
        //cout << endl;
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47188 KB Output is correct
2 Correct 24 ms 47244 KB Output is correct
3 Correct 24 ms 47200 KB Output is correct
4 Correct 25 ms 47224 KB Output is correct
5 Correct 26 ms 47316 KB Output is correct
6 Correct 24 ms 47248 KB Output is correct
7 Correct 25 ms 47188 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 777 ms 81780 KB Output is correct
2 Correct 1441 ms 193024 KB Output is correct
3 Execution timed out 1597 ms 316248 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47188 KB Output is correct
2 Correct 24 ms 47244 KB Output is correct
3 Correct 24 ms 47200 KB Output is correct
4 Correct 25 ms 47224 KB Output is correct
5 Correct 26 ms 47316 KB Output is correct
6 Correct 24 ms 47248 KB Output is correct
7 Correct 25 ms 47188 KB Output is correct
8 Correct 777 ms 81780 KB Output is correct
9 Correct 1441 ms 193024 KB Output is correct
10 Execution timed out 1597 ms 316248 KB Time limit exceeded
11 Halted 0 ms 0 KB -