oj.uz

Submission #629515

# Submission time Handle Problem Language Result Execution time Memory
629515 2022-08-14T15:09:29 Z vovamr Radio (COCI22_radio) C++17
40 / 110
 596 ms 144356 KB 
#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], cr[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) {
		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;
		cr[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, cr[x] = +iinf;
				for (int &d : fact[x]) {
					auto it = occ[d].lower_bound(x);
					if (it != occ[d].end()) chmin(cr[x], *it);
					if (it != occ[d].begin()) chmax(cl[x], *--it);
				}
				for (int &d : fact[x]) occ[d].insert(x);

				upd(x, cl[x]);
				if (cr[x] != +iinf) {
					chmax(cl[cr[x]], x);
					upd(cr[x], cl[cr[x]]);
				}
				if (cl[x] != -iinf) chmin(cr[cl[x]], x);
			}
			else {
				upd(x, -iinf);
				for (int &d : fact[x]) occ[d].erase(x);

				if (cl[x] != -iinf) {
					int a = cl[x]; cr[a] = +iinf;
					for (int &d : fact[a]) {
						auto it = occ[d].upper_bound(a);
						if (it != occ[d].end()) chmin(cr[a], *it);
					}
				}
				if (cr[x] != +iinf) {
					int a = cr[x]; cl[a] = -iinf;
					for (int &d : fact[a]) {
						auto it = occ[d].lower_bound(a);
						if (it != occ[d].begin()) chmax(cl[a], *--it);
					}
					upd(a, cl[a]);
				}
				cl[x] = -iinf;
				cr[x] = +iinf;
			}

//			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 215 ms 114776 KB Output is correct
2 Correct 181 ms 114776 KB Output is correct
3 Correct 183 ms 114852 KB Output is correct
4 Correct 182 ms 114772 KB Output is correct
5 Correct 175 ms 114764 KB Output is correct
6 Correct 201 ms 114840 KB Output is correct
7 Correct 182 ms 114764 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 121564 KB Output is correct
2 Correct 596 ms 135348 KB Output is correct
3 Correct 596 ms 144356 KB Output is correct
4 Correct 228 ms 115968 KB Output is correct
5 Correct 218 ms 120612 KB Output is correct
6 Correct 259 ms 126532 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 114776 KB Output is correct
2 Correct 181 ms 114776 KB Output is correct
3 Correct 183 ms 114852 KB Output is correct
4 Correct 182 ms 114772 KB Output is correct
5 Correct 175 ms 114764 KB Output is correct
6 Correct 201 ms 114840 KB Output is correct
7 Correct 182 ms 114764 KB Output is correct
8 Correct 384 ms 121564 KB Output is correct
9 Correct 596 ms 135348 KB Output is correct
10 Correct 596 ms 144356 KB Output is correct
11 Correct 228 ms 115968 KB Output is correct
12 Correct 218 ms 120612 KB Output is correct
13 Correct 259 ms 126532 KB Output is correct
14 Incorrect 305 ms 115040 KB Output isn't correct
15 Halted 0 ms 0 KB -