Submission #1003619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003619		Nailuj_217	Radio (COCI22_radio)	C++17	110 / 110	1270 ms	250472 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70