oj.uz

Submission #863724

# Submission time Handle Problem Language Result Execution time Memory
863724 2023-10-20T18:17:12 Z Irate Radio (COCI22_radio) C++14
40 / 110
 127 ms 22384 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4184 KB Output is correct
2 Correct 6 ms 4188 KB Output is correct
3 Correct 8 ms 4188 KB Output is correct
4 Correct 6 ms 4184 KB Output is correct
5 Correct 6 ms 4188 KB Output is correct
6 Correct 6 ms 4364 KB Output is correct
7 Correct 7 ms 4440 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 6036 KB Output is correct
2 Correct 124 ms 12696 KB Output is correct
3 Correct 127 ms 21016 KB Output is correct
4 Correct 15 ms 5980 KB Output is correct
5 Correct 47 ms 13448 KB Output is correct
6 Correct 94 ms 22384 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4184 KB Output is correct
2 Correct 6 ms 4188 KB Output is correct
3 Correct 8 ms 4188 KB Output is correct
4 Correct 6 ms 4184 KB Output is correct
5 Correct 6 ms 4188 KB Output is correct
6 Correct 6 ms 4364 KB Output is correct
7 Correct 7 ms 4440 KB Output is correct
8 Correct 82 ms 6036 KB Output is correct
9 Correct 124 ms 12696 KB Output is correct
10 Correct 127 ms 21016 KB Output is correct
11 Correct 15 ms 5980 KB Output is correct
12 Correct 47 ms 13448 KB Output is correct
13 Correct 94 ms 22384 KB Output is correct
14 Incorrect 122 ms 5664 KB Output isn't correct
15 Halted 0 ms 0 KB -