| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 866699 |
2023-10-26T18:43:17 Z |
TAhmed33 |
Radio (COCI22_radio) |
C++ |
|
481 ms |
108228 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 25;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
struct SegmentTree {
int tree[2 * MAXN];
void build (int l, int r, int node) {
if (l == r) {
tree[node] = MAXN;
} else {
build(l, mid, tl); build(mid + 1, r, tr);
tree[node] = min(tree[tl], tree[tr]);
}
}
void update (int l, int r, int a, int b, bool flag, int node) {
if (l > a || r < a) return;
if (l == r) {
if (flag) tree[node] = b;
else tree[node] = min(tree[node], b);
return;
}
update(l, mid, a, b, flag, tl); update(mid + 1, r, a, b, flag, tr);
tree[node] = min(tree[tl], tree[tr]);
}
int get (int l, int r, int a, int b, int node) {
if (l > b || r < a) return MAXN;
if (l >= a && r <= b) return tree[node];
return min(get(l, mid, a, b, tl), get(mid + 1, r, a, b, tr));
}
} cur;
int sieve[MAXN];
vector <int> get (int x) {
vector <int> y;
while (x > 1) {
y.push_back(sieve[x]);
x /= sieve[x];
}
y.resize(unique(y.begin(), y.end()) - y.begin());
return y;
}
int sze[MAXN], lst[MAXN][7];
int n, q;
set <int> active[MAXN];
bitset <MAXN> isactive;
void activate (int x) {
isactive[x] = 1;
int mn = MAXN;
for (int i = 0; i < sze[x]; i++) {
if (!active[lst[x][i]].empty()) {
auto g = active[lst[x][i]].lower_bound(x);
if (g != active[lst[x][i]].end()) mn = min(mn, *g);
if (g != active[lst[x][i]].begin()) {
g--;
cur.update(1, n, *g, x, 0, 1);
}
}
active[lst[x][i]].insert(x);
}
cur.update(1, n, x, mn, 1, 1);
}
void change (int x) {
int mn = MAXN;
for (int i = 0; i < sze[x]; i++) {
if (active[lst[x][i]].empty()) continue;
auto g = active[lst[x][i]].lower_bound(x);
if (g != active[lst[x][i]].end()) mn = min(mn, *g);
}
cur.update(1, n, x, mn, 1, 1);
}
void deactivate (int x) {
isactive[x] = 0;
cur.update(1, n, x, MAXN, 1, 1);
for (int i = 0; i < sze[x]; i++) {
active[lst[x][i]].erase(x);
if (active[lst[x][i]].empty()) continue;
auto g = active[lst[x][i]].lower_bound(x);
if (g != active[lst[x][i]].begin()) {
g--;
change(*g);
}
}
}
int main () {
for (int i = 1; i < MAXN; i++) sieve[i] = i;
for (int i = 2; i * i < MAXN; i++) {
if (sieve[i] == i) for (int j = i; j < MAXN; j += i) sieve[j] = i;
}
for (int i = 1; i < MAXN; i++) {
auto x = get(i);
sze[i] = x.size();
for (int j = 0; j < sze[i]; j++) lst[i][j] = x[j];
}
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
cur.build(1, n, 1);
while (q--) {
char z;
cin >> z;
if (z == 'S') {
int x;
cin >> x;
if (isactive[x]) {
deactivate(x);
} else {
activate(x);
}
} else {
int l, r;
cin >> l >> r;
if (cur.get(1, n, l, r, 1) <= r) cout << "DA\n";
else cout << "NE\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
84564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
289 ms |
90196 KB |
Output is correct |
| 2 |
Correct |
429 ms |
101452 KB |
Output is correct |
| 3 |
Correct |
481 ms |
108228 KB |
Output is correct |
| 4 |
Correct |
106 ms |
84556 KB |
Output is correct |
| 5 |
Correct |
138 ms |
86632 KB |
Output is correct |
| 6 |
Correct |
161 ms |
90452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
84564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
