oj.uz

Submission #629508

# Submission time Handle Problem Language Result Execution time Memory
629508 2022-08-14T14:56:54 Z vovamr Radio (COCI22_radio) C++17
40 / 110
 633 ms 145840 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 + 10;
ve<int> pr; int lp[N];

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

int cl[N], cr[N];

int n;
int t[2 * N];
inline void build() { fill(t, t + 2 * n + 5, 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 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 171 ms 107096 KB Output is correct
2 Correct 179 ms 107016 KB Output is correct
3 Correct 184 ms 106996 KB Output is correct
4 Correct 171 ms 107008 KB Output is correct
5 Correct 172 ms 106992 KB Output is correct
6 Correct 178 ms 106924 KB Output is correct
7 Correct 179 ms 107084 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 115792 KB Output is correct
2 Correct 633 ms 132844 KB Output is correct
3 Correct 612 ms 145840 KB Output is correct
4 Correct 177 ms 109048 KB Output is correct
5 Correct 212 ms 117560 KB Output is correct
6 Correct 262 ms 127992 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 107096 KB Output is correct
2 Correct 179 ms 107016 KB Output is correct
3 Correct 184 ms 106996 KB Output is correct
4 Correct 171 ms 107008 KB Output is correct
5 Correct 172 ms 106992 KB Output is correct
6 Correct 178 ms 106924 KB Output is correct
7 Correct 179 ms 107084 KB Output is correct
8 Correct 385 ms 115792 KB Output is correct
9 Correct 633 ms 132844 KB Output is correct
10 Correct 612 ms 145840 KB Output is correct
11 Correct 177 ms 109048 KB Output is correct
12 Correct 212 ms 117560 KB Output is correct
13 Correct 262 ms 127992 KB Output is correct
14 Incorrect 289 ms 108588 KB Output isn't correct
15 Halted 0 ms 0 KB -