#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 {{}, 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 |
Incorrect |
84 ms |
180260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
333 ms |
191060 KB |
Output is correct |
| 2 |
Correct |
641 ms |
219528 KB |
Output is correct |
| 3 |
Correct |
870 ms |
248460 KB |
Output is correct |
| 4 |
Incorrect |
145 ms |
184996 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
84 ms |
180260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
