Submission #863724

#	Time	Username	Problem	Language	Result	Execution time	Memory
863724		Irate	Radio (COCI22_radio)	C++14	40 / 110	127 ms	22384 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int mxN = 1e6 + 1;
int cnt[mxN];
bool is[mxN];
int gcd(int a, int b){
    if(b == 0)return a;
    return gcd(b, a % b);
}
struct SegmentTree{
    vector<int>sTree;
    SegmentTree(int n){
        sTree.resize(4 * n);
    }
    void Update(int node, int l, int r, int pos, int val){
        if(l == r){
            sTree[node] += val;
        }
        else{
            int mid = (l + r) >> 1;
            if(pos <= mid)Update(node * 2, l, mid, pos, val);
            else Update(node * 2 + 1, mid + 1, r, pos, val);
            sTree[node] = max(sTree[node * 2], sTree[node * 2 + 1]);
        }
    }
    int Query(int node, int l, int r, int ql, int qr){
        if(ql <= l && r <= qr)return sTree[node];
        if(ql > r || l > qr)return -1e9;
        int mid = (l + r) >> 1;
        int lc = Query(node * 2, l, mid, ql, qr);
        int rc = Query(node * 2 + 1, mid + 1, r, ql, qr);
        return max(lc, rc);
    }
    int Get(int node, int l, int r, int pos){
        if(l == r)return sTree[node];
        int mid = (l + r) >> 1;
        if(pos <= mid)return Get(node * 2, l, mid, pos);
        return Get(node * 2 + 1, mid + 1, r, pos);
    }
};
int main()
{
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int>sieve(1e6 + 6, 1e9);
    sieve[1] = 1;
    for(int i = 2;i <= 1e6;++i){
        if(sieve[i] == 1e9){
            for(int j = i;j <= 1e6;j += i){
                sieve[j] = min(sieve[j], i);
            }
        }
    }
    SegmentTree tree(n);
    if(n <= 100 && q <= 200){
        while(q--){
            char type;
            cin >> type;
            if(type == 'C'){
                int l, r;
                cin >> l >> r;
                vector<int>v;
                for(int i = l;i <= r;++i){
                    if(is[i])v.push_back(i);
                }
                bool found = 0;
                for(int i = 0;i < v.size();++i){
                    for(int j = i + 1;j < v.size();++j){
                        if(gcd(v[i], v[j]) > 1){
                            found = 1;
                            break;
                        }
                    }
                    if(found)break;
                }
                if(found){
                    cout << "DA\n";
                }
                else{
                    cout << "NE\n";
                }
            }
            else{
                int pos;
                cin >> pos;
                is[pos] ^= 1;
            }
        }
    }
    else{
        while(q--){
            char type;
            cin >> type;
            if(type == 'S'){
                int pos, cpy;
                cin >> pos;
                cpy = pos;
                vector<int>primes;
                while(pos != 1){
                    int p = sieve[pos];
                    primes.push_back(p);
                    while(pos % p == 0){
                        pos /= p;
                    }
                }
                if(is[cpy]){
                    for(int &i : primes){
                        tree.Update(1, 1, n, i, -1);
                    }
                }
                else{
                    for(int &i : primes){
                        tree.Update(1, 1, n, i, 1);
                    }
                }
                is[cpy] ^= 1;
            }
            else{
                int l, r;
                cin >> l >> r;
                int Q = tree.Query(1, 1, n, l, r);
                if(Q > 1)cout << "DA\n";
                else cout << "NE\n";
            }
        }
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:69:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |                 for(int i = 0;i < v.size();++i){
      |                               ~~^~~~~~~~~~
Main.cpp:70:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |                     for(int j = i + 1;j < v.size();++j){
      |                                       ~~^~~~~~~~~~

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