oj.uz

답안 #629539

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
629539 2022-08-14T15:21:30 Z vovamr Radio (COCI22_radio) C++17
110 / 110
 724 ms 144864 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];

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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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