oj.uz

답안 #880764

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
880764 2023-11-30T03:10:25 Z tsumondai Radio (COCI22_radio) C++14
110 / 110
 550 ms 46544 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int MAXN = 1 << 20;

const int oo = 1e9, mod = 1e9 + 7;

int n, q;
bool on[MAXN];
unordered_map<int, set<int>> transmitting;
int seg[2 * MAXN][2];

int sieve[MAXN];
void init_sieve() {
	foru(i, 2, MAXN - 1) {
		if (sieve[i] == 0) {
			for (int j = i; j < MAXN; j += i) {
				sieve[j] = i;
			}
		}
	}
}

void init_segtree() {
	foru(i, 0, 2 * MAXN - 1) {
		seg[i][0] = -1;
		seg[i][1] = MAXN;
	}
}

void update_segtree(int idx, int vl, int vr) {
	idx += MAXN;
	seg[idx][0] = vl;
	seg[idx][1] = vr;
	for (idx /= 2; idx > 0; idx /= 2) {
		seg[idx][0] = max(seg[2 * idx][0], seg[2 * idx + 1][0]);
		seg[idx][1] = min(seg[2 * idx][1], seg[2 * idx + 1][1]);
	}
}

ii query_segtree(int left, int right, int node = 1, int nl = 0, int nr = MAXN - 1) {
	if (left > nr || right < nl) return ii(-1, MAXN);
	if (left <= nl && nr <= right) return ii(seg[node][0], seg[node][1]);
	ii a = query_segtree(left, right, 2 * node, nl, nl + (nr - nl) / 2);
	ii b = query_segtree(left, right, 2 * node + 1, nl + (nr - nl) / 2 + 1, nr);
	return ii(max(a.first, b.first), min(a.second, b.second));
}

void fixup_segtree(int x) {
	int left = -1, right = MAXN;
	for (int p = sieve[x], tmp = x; tmp != 1;) {
		auto& ps = transmitting[p];

		auto lit = ps.lower_bound(x);
		if (lit != ps.begin()) {
			lit--;
			left = max(left, *lit);
		}

		auto rit = ps.upper_bound(x);
		if (rit != ps.end()) right = min(right, *rit);

		while (tmp % p == 0) {
			tmp /= p;
		}
		p = sieve[tmp];
	}
	update_segtree(x, left, right);
}
int get_left(int x) {
	return seg[MAXN + x][0];
}
int get_right(int x) {
	return seg[MAXN + x][1];
}

void switch_station(int x) {
	if (x == 1) return;
	vector<int> changed;
	int left = -1, right = MAXN;
	for (int p = sieve[x], tmp = x; tmp != 1;) {
		auto& ps = transmitting[p];

		auto lit = ps.lower_bound(x);
		if (lit != ps.begin()) {
			lit--;
			if (!on[x] && get_right(*lit) > x) {
				update_segtree(*lit, get_left(*lit), x);
			} else if (on[x] && get_right(*lit) == x) {
				changed.push_back(*lit);
			}
			left = max(*lit, left);
		}

		auto rit = ps.upper_bound(x);
		if (rit != ps.end()) {
			if (!on[x] && get_left(*rit) < x) {
				update_segtree(*rit, x, get_right(*rit));
			} else if (on[x] && get_left(*rit) == x) {
				changed.push_back(*rit);
			}
			right = min(*rit, right);
		}
		if (!on[x]) ps.insert(x);
		else ps.erase(x);

		while (tmp % p == 0) {
			tmp /= p;
		}
		p = sieve[tmp];
	}
	if (on[x]) {
		update_segtree(x, -1, MAXN);
		on[x] = false;
	} else {
		update_segtree(x, left, right);
		on[x] = true;
	}
	sort(changed.begin(), changed.end());
	changed.erase(unique(changed.begin(), changed.end()), changed.end());
	for (int i : changed) {
		fixup_segtree(i);
	}
}

bool noisy(int l, int r) {
	ii x = query_segtree(l, r);
	//printf("%d %d\n", x.first, x.second);
	return x.first >= l || x.second <= r;
}

void process() {
	cin >> n >> q;
	for (int i = 0; i < q; i++) {
		char s;
		cin >> s;
		if (s == 'S') {
			int x;
			cin >> x;
			switch_station(x);
		} else if (s == 'C') {
			int l, r;

			cin >> l >> r;
			if (noisy(l, r)) {
				cout << "DA\n";
			} else {
				cout << "NE\n";
			}
		}
	}
	return;
}

signed main() {
	cin.tie(0)->sync_with_stdio(false);
	//freopen(".inp", "r", stdin);
	//freopen(".out", "w", stdout);
	init_sieve();
	init_segtree();
	process();
	cerr << "Time elapsed: " << __TIME << " s.\n";
	return 0;
}

/*
Xét các trường hợp đặc biệt
Kiểm tra lại input/output
Cố gắng trâu
Lật ngược bài toán
Keep calm and get VOI
Flow:

*/

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 21084 KB Output is correct
2 Correct 8 ms 21084 KB Output is correct
3 Correct 8 ms 21116 KB Output is correct
4 Correct 8 ms 21080 KB Output is correct
5 Correct 7 ms 21084 KB Output is correct
6 Correct 8 ms 21116 KB Output is correct
7 Correct 8 ms 21152 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 202 ms 28500 KB Output is correct
2 Correct 391 ms 39180 KB Output is correct
3 Correct 432 ms 43640 KB Output is correct
4 Correct 13 ms 21852 KB Output is correct
5 Correct 35 ms 24760 KB Output is correct
6 Correct 74 ms 28068 KB Output is correct

Subtask #3
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 21084 KB Output is correct
2 Correct 8 ms 21084 KB Output is correct
3 Correct 8 ms 21116 KB Output is correct
4 Correct 8 ms 21080 KB Output is correct
5 Correct 7 ms 21084 KB Output is correct
6 Correct 8 ms 21116 KB Output is correct
7 Correct 8 ms 21152 KB Output is correct
8 Correct 202 ms 28500 KB Output is correct
9 Correct 391 ms 39180 KB Output is correct
10 Correct 432 ms 43640 KB Output is correct
11 Correct 13 ms 21852 KB Output is correct
12 Correct 35 ms 24760 KB Output is correct
13 Correct 74 ms 28068 KB Output is correct
14 Correct 186 ms 22612 KB Output is correct
15 Correct 350 ms 26348 KB Output is correct
16 Correct 547 ms 46544 KB Output is correct
17 Correct 476 ms 42912 KB Output is correct
18 Correct 550 ms 44976 KB Output is correct
19 Correct 504 ms 44768 KB Output is correct
20 Correct 84 ms 28120 KB Output is correct
21 Correct 78 ms 28228 KB Output is correct
22 Correct 74 ms 28252 KB Output is correct
23 Correct 97 ms 28244 KB Output is correct