oj.uz

Submission #629509

# Submission time Handle Problem Language Result Execution time Memory
629509 2022-08-14T14:59:22 Z vovamr Radio (COCI22_radio) C++17
40 / 110
 610 ms 144352 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 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);

	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 172 ms 107084 KB Output is correct
2 Correct 175 ms 107088 KB Output is correct
3 Correct 172 ms 107020 KB Output is correct
4 Correct 177 ms 107084 KB Output is correct
5 Correct 177 ms 107084 KB Output is correct
6 Correct 170 ms 107012 KB Output is correct
7 Correct 175 ms 106972 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 114608 KB Output is correct
2 Correct 610 ms 131492 KB Output is correct
3 Correct 583 ms 144352 KB Output is correct
4 Correct 181 ms 108964 KB Output is correct
5 Correct 219 ms 116904 KB Output is correct
6 Correct 257 ms 126544 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 107084 KB Output is correct
2 Correct 175 ms 107088 KB Output is correct
3 Correct 172 ms 107020 KB Output is correct
4 Correct 177 ms 107084 KB Output is correct
5 Correct 177 ms 107084 KB Output is correct
6 Correct 170 ms 107012 KB Output is correct
7 Correct 175 ms 106972 KB Output is correct
8 Correct 387 ms 114608 KB Output is correct
9 Correct 610 ms 131492 KB Output is correct
10 Correct 583 ms 144352 KB Output is correct
11 Correct 181 ms 108964 KB Output is correct
12 Correct 219 ms 116904 KB Output is correct
13 Correct 257 ms 126544 KB Output is correct
14 Incorrect 306 ms 107240 KB Output isn't correct
15 Halted 0 ms 0 KB -