#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()) {
| ~~~^~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
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 |
| # |
결과 |
실행 시간 |
메모리 |
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 |
| # |
결과 |
실행 시간 |
메모리 |
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 |
