Submission #936011

#	Time	Username	Problem	Language	Result	Execution time	Memory
936011		MinaRagy06	Joker (BOI20_joker)	C++17	100 / 100	355 ms	51380 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define md ((l + r) >> 1)

const int N = 200'005;
int par[N], sz[N], dep[N];
int gud;
array<int, 2> find(int u) {
	if (par[u] == u) {
		return {u, 0};
	}
	array<int, 2> v = find(par[u]);
	v[1] ^= dep[u];
	return v;
}
vector<pair<int*, int>> logs;
void assign(int *x, int y) {
	logs.push_back({x, *x});
	*x = y;
}
void rollback() {
	while (logs.back().first) {
		pair<int*, int> v = logs.back();
		logs.pop_back();
		*v.first = v.second;
	}
	logs.pop_back();
}
void join(int u, int v) {
	array<int, 2> pu = find(u), pv = find(v);
	if (pu[0] == pv[0]) {
		assign(&gud, gud && (dep[pv[0]] == (pv[1] ^ pu[1] ^ 1)));
		return;
	}
	if (sz[pu[0]] < sz[pv[0]]) {
		swap(u, v);
		swap(pu, pv);
	}
	assign(&par[pv[0]], pu[0]);
	assign(&dep[pv[0]], (pv[1] ^ pu[1] ^ 1));
	assign(&sz[pu[0]], sz[pu[0]] + sz[pv[0]]);
}
array<int, 2> a[N];
vector<int> seg[1 << 19];
void add(int i, int l, int r, int s, int e, int x) {
	if (s <= l && r <= e) {
		seg[i].push_back(x);
		return;
	}
	if (r < s || e < l) {
		return;
	}
	add(i << 1, l, md, s, e, x);
	add(i << 1 | 1, md + 1, r, s, e, x);
}
int ptr, mn;
int suf[N];
void solve(int i, int l, int r) {
	logs.push_back({NULL, 0});
	for (auto j : seg[i]) {
		join(a[j][0], a[j][1]);
	}
	if (l == r) {
		while (gud && l < ptr - 1) {
			assign(&ptr, ptr - 1);
			join(a[ptr][0], a[ptr][1]);
			mn = min(mn, ptr);
		}
		if (!gud) suf[l] = ptr;
	} else {
		solve(i << 1 | 1, md + 1, r);
		solve(i << 1, l, md);
	}
	rollback();
	while (ptr > mn) {
		assign(&ptr, ptr - 1);
		join(a[ptr][0], a[ptr][1]);
	}
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		cin >> a[i][0] >> a[i][1];
	}
	for (int i = 1; i <= m; i++) {
		add(1, 0, m, i, m, i);
	}
	for (int i = 0; i <= m; i++) {
		suf[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		par[i] = i;
		sz[i] = 1;
		dep[i] = 0;
	}
	gud = 1;
	ptr = mn = m + 1;
	solve(1, 0, m);
// 	for (int i = 0; i <= m; i++) {
// 		cout << suf[i] << ' ';
// 	}
// 	cout << '\n';
	while (q--) {
		int l, r;
		cin >> l >> r;
		if (r < suf[l - 1]) {
			cout << "YES\n";
		} else {
			cout << "NO\n";
		}
	}
	return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 25 / 25
• Subtask 4: 10 / 10
• Subtask 5: 22 / 22
• Subtask 6: 29 / 29