oj.uz

Submission #1003619

# Submission time Handle Problem Language Result Execution time Memory
1003619 2024-06-20T13:59:27 Z Nailuj_217 Radio (COCI22_radio) C++17
110 / 110
 1270 ms 250472 KB 
#include <bits/stdc++.h>
#define l long long
using namespace std;

const l LEN = 1000005;

array<pair<vector<l>, bool>, LEN*5+5> tree; 

bitset<LEN> sending;

array<vector<l>, LEN> primefactors;

pair<vector<l>, bool> mrg(pair<vector<l>, bool> a, pair<vector<l>, bool> b) {
    if (a.second || b.second) return {{}, true};
    pair<vector<l>, bool> c;
    l ac = 0, bc = 0;
    while (ac < a.first.size() || bc < b.first.size()) {
        if (ac < a.first.size() && bc < b.first.size() && a.first[ac] == b.first[bc]) {
            c.second = true;
            c.first = {};
            return c;
        } if (ac >= a.first.size()) {
            c.first.push_back(b.first[bc++]);
        } else if (bc >= b.first.size()) {
            c.first.push_back(a.first[ac++]);
        } else if (a.first[ac] < b.first[bc]) {
            c.first.push_back(a.first[ac++]);
        } else {
            c.first.push_back(b.first[bc++]);
        }
    }
    return c;
}



pair<vector<l>, bool> insertnum(l i, l s, l f, l k) {
    if (k < s || k > f) return tree[i];
    if (s == f) {
        return tree[i] = {primefactors[s], false};
    }
    pair<vector<l>, bool> left, right;
    left = insertnum(i*2, s, (s+f)/2, k);
    right = insertnum(i*2+1, (s+f)/2+1, f, k);

    return tree[i] = mrg(left, right);
}

pair<vector<l>, bool> erasenum(l i, l s, l f, l k) {
    if (k < s || k > f) return tree[i];
    if (s == f) {
        return tree[i] = {{}, false};
    }
    pair<vector<l>, bool> left, right;
    left = erasenum(i*2, s, (s+f)/2, k);
    right = erasenum(i*2+1, (s+f)/2+1, f, k);

    return tree[i] = mrg(left, right);
}


pair<vector<l>, bool> querynum(l i, l s, l f, l a, l b) {
    if (a > f || b < s) return {{}, false};
    if (a <= s && b >= f) return tree[i]; 
    pair<vector<l>, bool> left, right;
    left = querynum(i*2, s, (s+f)/2, a, b);
    right = querynum(i*2+1, (s+f)/2+1, f, a, b);

    return mrg(left, right);
}


int main() {

    l n;
    int q;
    cin >> n >> q;
    string s;
    l a, b;
    for (int i = 2; i <= n; i++) {
        if (!primefactors[i].empty()) continue;
        for (int j = i; j <= n; j += i) {
            primefactors[j].push_back(i);
        }
    }
    while (q--) {

        cin >> s;
        
        if (s == "S") {
            cin >> a;
            if (sending[a]) {
                sending[a] = 0;
                erasenum(1, 1, n, a);
            } else {
                sending[a] = 1;
                insertnum(1, 1, n, a);
            }
            
        } else {
            cin >> a >> b;
            if (querynum(1, 1, n, a, b).second) cout << "DA" << endl;
            else cout << "NE" << endl;
        }

        b = a;

    }





    return 0;
}

Compilation message

Main.cpp: In function 'std::pair<std::vector<long long int>, bool> mrg(std::pair<std::vector<long long int>, bool>, std::pair<std::vector<long long int>, bool>)':
Main.cpp:17:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     while (ac < a.first.size() || bc < b.first.size()) {
      |            ~~~^~~~~~~~~~~~~~~~
Main.cpp:17:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     while (ac < a.first.size() || bc < b.first.size()) {
      |                                   ~~~^~~~~~~~~~~~~~~~
Main.cpp:18:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         if (ac < a.first.size() && bc < b.first.size() && a.first[ac] == b.first[bc]) {
      |             ~~~^~~~~~~~~~~~~~~~
Main.cpp:18:39: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         if (ac < a.first.size() && bc < b.first.size() && a.first[ac] == b.first[bc]) {
      |                                    ~~~^~~~~~~~~~~~~~~~
Main.cpp:22:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         } if (ac >= a.first.size()) {
      |               ~~~^~~~~~~~~~~~~~~~~
Main.cpp:24:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         } else if (bc >= b.first.size()) {
      |                    ~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 180308 KB Output is correct
2 Correct 72 ms 180304 KB Output is correct
3 Correct 73 ms 180308 KB Output is correct
4 Correct 71 ms 180308 KB Output is correct
5 Correct 72 ms 180304 KB Output is correct
6 Correct 67 ms 180304 KB Output is correct
7 Correct 71 ms 180404 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 190332 KB Output is correct
2 Correct 497 ms 218964 KB Output is correct
3 Correct 817 ms 247892 KB Output is correct
4 Correct 120 ms 184912 KB Output is correct
5 Correct 478 ms 204368 KB Output is correct
6 Correct 1012 ms 228852 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 180308 KB Output is correct
2 Correct 72 ms 180304 KB Output is correct
3 Correct 73 ms 180308 KB Output is correct
4 Correct 71 ms 180308 KB Output is correct
5 Correct 72 ms 180304 KB Output is correct
6 Correct 67 ms 180304 KB Output is correct
7 Correct 71 ms 180404 KB Output is correct
8 Correct 278 ms 190332 KB Output is correct
9 Correct 497 ms 218964 KB Output is correct
10 Correct 817 ms 247892 KB Output is correct
11 Correct 120 ms 184912 KB Output is correct
12 Correct 478 ms 204368 KB Output is correct
13 Correct 1012 ms 228852 KB Output is correct
14 Correct 307 ms 181844 KB Output is correct
15 Correct 331 ms 186708 KB Output is correct
16 Correct 825 ms 250472 KB Output is correct
17 Correct 839 ms 247608 KB Output is correct
18 Correct 854 ms 248996 KB Output is correct
19 Correct 817 ms 249252 KB Output is correct
20 Correct 1038 ms 228848 KB Output is correct
21 Correct 1270 ms 229156 KB Output is correct
22 Correct 1241 ms 228944 KB Output is correct
23 Correct 1184 ms 228944 KB Output is correct