Submission #629539

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
629539	2022-08-14T15:21:30 Z	vovamr	Radio (COCI22_radio)	C++17	110 / 110	724 ms	144864 KB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int N = 1e6 + 100;
ve<int> pr; int lp[N];

ve<int> fact[N];
set<int> occ[N];

int cl[N];

int t[2 * N];
inline void build() { fill(t, t + 2 * N, -iinf); }
inline void upd(int i, int x) {
	t[i += N] = x;
	while (i > 1) { t[i >> 1] = max(t[i], t[i ^ 1]); i >>= 1; }
}
inline int get(int l, int r) {
	int res = -iinf;
	l += N, r += N + 1;
	while (l < r) {
		if (l & 1) chmax(res, t[l++]);
		if (r & 1) chmax(res, t[--r]);
		l >>= 1, r >>= 1;
	} return res;
}

inline void solve() {
	for (int i = 2; i < N; ++i) {
		if (!lp[i]) lp[i] = i, pr.pb(i);
		for (int j = 0; j < sz(pr) && i * pr[j] < N && pr[j] <= lp[i]; ++j) {
			lp[i * pr[j]] = pr[j];
		}
	}
//	for (int i = 2; i < N; ++i) {
//		if (lp[i] < i) continue;
//		for (int j = i; j < N; j += i) fact[j].pb(i);
//	}
	for (int i = 2; i < N; ++i) {
		int x = i;
		while (x > 1) {
			int d = lp[x]; fact[i].pb(d);
			while (x % d == 0) x /= d;
		}
	}

	int n, q;
	cin >> n >> q;

	ve<int> active(n + 1);
	for (int i = 1; i <= n; ++i) cl[i] = -iinf;
	build();

	while (q--) {
		char te;
		cin >> te;
		if (te == 'S') {
			int x;
			cin >> x;
			active[x] ^= 1;

			if (active[x]) {
				cl[x] = -iinf;
				for (int &d : fact[x]) {
					auto it = occ[d].lower_bound(x);
					int right = it != occ[d].end() ? *it : iinf;
					int left = it != occ[d].begin() ? *--it : -iinf;

					chmax(cl[x], left);
					if (right != iinf) {
						if (cl[right] < x) {
							cl[right] = x;
							upd(right, cl[right]);
						}
					}
				}
				for (int &d : fact[x]) occ[d].insert(x);
				upd(x, cl[x]);
			}
			else {
				upd(x, -iinf); cl[x] = -iinf;
				for (int &d : fact[x]) occ[d].erase(x);
				for (int &d : fact[x]) {
					auto it = occ[d].lower_bound(x);
					int right = it != occ[d].end() ? *it : iinf;

					if (right != iinf) {
						cl[right] = -iinf;
						for (int &f : fact[right]) {
							auto it1 = occ[f].lower_bound(right);
							if (it1 != occ[f].begin()) chmax(cl[right], *--it1);
						}
						upd(right, cl[right]);
					}
				}
			}

//			for (int i = 1; i <= n; ++i) {
//				if (!active[i]) continue;
//				cout << i << " -> (" << cl[i] << ", " << cr[i] << ")" << '\n';
//			}
//			cout << '\n';
		}
		else {
			int l, r;
			cin >> l >> r;
			if (get(l, r) >= l) cout << "DA" << '\n';
			else cout << "NE" << '\n';
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	178 ms	114760 KB	Output is correct
2	Correct	177 ms	114800 KB	Output is correct
3	Correct	170 ms	114844 KB	Output is correct
4	Correct	174 ms	114764 KB	Output is correct
5	Correct	179 ms	114764 KB	Output is correct
6	Correct	180 ms	114944 KB	Output is correct
7	Correct	181 ms	114740 KB	Output is correct

Subtask #2

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	408 ms	121232 KB	Output is correct
2	Correct	587 ms	133444 KB	Output is correct
3	Correct	605 ms	140480 KB	Output is correct
4	Correct	183 ms	115512 KB	Output is correct
5	Correct	202 ms	118784 KB	Output is correct
6	Correct	257 ms	122640 KB	Output is correct

Subtask #3

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	178 ms	114760 KB	Output is correct
2	Correct	177 ms	114800 KB	Output is correct
3	Correct	170 ms	114844 KB	Output is correct
4	Correct	174 ms	114764 KB	Output is correct
5	Correct	179 ms	114764 KB	Output is correct
6	Correct	180 ms	114944 KB	Output is correct
7	Correct	181 ms	114740 KB	Output is correct
8	Correct	408 ms	121232 KB	Output is correct
9	Correct	587 ms	133444 KB	Output is correct
10	Correct	605 ms	140480 KB	Output is correct
11	Correct	183 ms	115512 KB	Output is correct
12	Correct	202 ms	118784 KB	Output is correct
13	Correct	257 ms	122640 KB	Output is correct
14	Correct	314 ms	115048 KB	Output is correct
15	Correct	542 ms	120128 KB	Output is correct
16	Correct	724 ms	144864 KB	Output is correct
17	Correct	581 ms	141284 KB	Output is correct
18	Correct	652 ms	143100 KB	Output is correct
19	Correct	654 ms	143032 KB	Output is correct
20	Correct	245 ms	124140 KB	Output is correct
21	Correct	274 ms	124140 KB	Output is correct
22	Correct	251 ms	124108 KB	Output is correct
23	Correct	248 ms	124364 KB	Output is correct