Submission #441231

#	Time	Username	Problem	Language	Result	Execution time	Memory
441231		ritul_kr_singh	Joker (BOI20_joker)	C++17	100 / 100	1665 ms	237476 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
// #define int long long
 
const int MAXN = 2e5, B = 850, NUM = MAXN / B + 2;
 
int a[NUM][MAXN];
bool p[NUM][MAXN], b[NUM];
int rollback[4][B+1];
int n, m, q, x[MAXN], y[MAXN], ans[MAXN+1], rP = 0, r, c = 1, L[MAXN], R[MAXN], cnt[MAXN+1];
int last[NUM];
 
void unite(int i){
	bool pS = 0, pT = 0;
	int u = x[i], v = y[i];
	while(a[r][u] >= 0) pS ^= p[r][u], u = a[r][u];
	while(a[r][v] >= 0) pT ^= p[r][v], v = a[r][v];
	if(u == v){
		b[r] = b[r] || (pS == pT);
		return;
	}
	if(a[r][u] > a[r][v]) swap(u, v);
	if(!c){
		rollback[0][rP] = u;
		rollback[1][rP] = v;
		rollback[2][rP] = a[r][v];
		rollback[3][rP] = p[r][v];
		++rP;
	}
	a[r][u] += a[r][v];
	a[r][v] = u;
	p[r][v] = pS ^ pT ^ 1;
}
 
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m >> q;
	for(int i=0; i<m; ++i){
		cin >> x[i] >> y[i], --x[i], --y[i];
 
		if(i % B) continue;
		r = i / B;
 
		if(i){
			b[r] = b[r-1];
			for(int j=0; j<n; ++j) a[r][j] = a[r-1][j];
			for(int j=0; j<n; ++j) p[r][j] = p[r-1][j];
			for(int j=i-B; j<i; ++j) unite(j);
		}else fill(a[r], a[r]+n, -1);
	}
	fill(last, last+NUM, m);
	for(int i=0; i<q; ++i){
		cin >> L[i] >> R[i];
		++cnt[R[i]];
	}
 
	int z = ++r;
	b[r] = b[r-1];
	for(int j=0; j<n; ++j) a[r][j] = a[r-1][j];
	for(int j=0; j<n; ++j) p[r][j] = p[r-1][j];
	for(int j=(r-1)*B; j<m; ++j) unite(j);
	if(!b[r]){
		while(q--) cout << "NO\n";
		return 0;
	}
 
	for(int i=m; i; --i){
		if(cnt[i] || i==m){
			c = 1;
			while(z && b[z-1]){
				--z;
				r = z-1;
				while(last[r] > i) unite(--last[r]);
			}
			if(!z) break;
	 
			r = z - 1, c = 0;
			int l = r*B;
			while(!b[r]) unite(l++);
			b[r] = 0, ans[i] = l;
	 
			while(rP){
				--rP;
				a[r][rollback[1][rP]] = rollback[2][rP];
				a[r][rollback[0][rP]] -= rollback[2][rP];
				p[r][rollback[1][rP]] = rollback[3][rP];
			}
		}
		c = 1, r = z-1;
		unite(i-1);
		--last[r];
	}
	for(int i=0; i<q; ++i){
		cout << (ans[R[i]] >= L[i] ? "NO" : "YES") << '\n';
	}
}

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