#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
const int N = 1e6 + 5;
int a[N], st[4 * N], sieve[N];
bool check[N];
priority_queue<int> pq[N];
set<int> s[N];
int merge(int x, int y) {
return min(x, y);
}
void build(int x, int tl, int tr) {
if (tl == tr) st[x] = 1e9;
else {
int tm = (tl + tr) / 2;
build(2 * x, tl, tm);
build(2 * x + 1, tm + 1, tr);
st[x] = 1e9;
}
}
void update(int x, int tl, int tr, int pos) {
if (tl == tr) {
if (!check[pos]) {
st[x] = 1e9;
return;
}
while (!pq[pos].empty() and !check[-pq[pos].top()]) pq[pos].pop();
if (pq[pos].empty()) st[x] = 1e9;
else st[x] = -pq[pos].top();
}
else {
int tm = (tl + tr) / 2;
if (pos <= tm) update(2 * x, tl, tm, pos);
else update(2 * x + 1, tm + 1, tr, pos);
st[x] = merge(st[2 * x], st[2 * x + 1]);
}
}
int get(int x, int tl, int tr, int l, int r) {
if (l <= tl and tr <= r) return st[x];
if (r < tl or l > tr) return 1e9;
int tm = (tl + tr) / 2;
return merge(get(2 * x, tl, tm, l, r), get(2 * x + 1, tm + 1, tr, l, r));
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n, q;
cin >> n >> q;
for (int i = 2; i * i <= n; i++) {
if (sieve[i] != 0) continue;
for (int j = i; j <= n; j += i) if (sieve[j] == 0) sieve[j] = i;
}
for (int i = 2; i <= n; i++) if (sieve[i] == 0) sieve[i] = i;
build(1, 1, n);
while (q--) {
char c;
cin >> c;
if (c == 'S') {
int x;
cin >> x;
if (x == 1) continue;
if (check[x]) {
check[x] = 0;
update(1, 1, n, x);
int tm = x;
while (tm > 1) {
int tm2 = sieve[tm];
while (tm % tm2 == 0) tm /= tm2;
s[tm2].erase(x);
if (s[tm2].empty()) continue;
auto it = s[tm2].upper_bound(x), it2 = it;
it--;
pq[*it].push(-*it2);
update(1, 1, n, *it);
}
}
else {
check[x] = 1;
int tm = x;
while (tm > 1) {
int tm2 = sieve[tm];
while (tm % tm2 == 0) tm /= tm2;
if (s[tm2].empty()) {
s[tm2].insert(x);
continue;
}
auto it = s[tm2].upper_bound(x);
if (it != s[tm2].begin()) {
it--;
pq[*it].push(-x);
update(1, 1, n, *it);
it++;
}
if (it != s[tm2].end()) pq[x].push(-*it);
s[tm2].insert(x);
}
}
}
else {
int l, r;
cin >> l >> r;
int ans = get(1, 1, n, l, r);
if (ans > r) cout << "NE\n";
else cout << "DA\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
78540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
245 ms |
89348 KB |
Output is correct |
| 2 |
Correct |
482 ms |
105552 KB |
Output is correct |
| 3 |
Correct |
603 ms |
115880 KB |
Output is correct |
| 4 |
Incorrect |
39 ms |
80204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
78540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
