Submission #970446

#	Time	Username	Problem	Language	Result	Execution time	Memory
970446		maxFedorchuk	Joker (BOI20_joker)	C++17	100 / 100	357 ms	16752 KiB

Joker

#include <bits/stdc++.h>
#define va first
#define vb second
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef pair<int,int> pii;
	
const int MN = 2e5+5;
	
int N,M,Q,pos;
int par[MN<<1],sz[MN<<1],ans[MN];
pii E[MN];
	
vector<pii> qu;
vector<int> cnt;
	
int fnd(int u)
{
	return u==par[u] ? u : fnd(par[u]);
}
	
void join(int u, int v)
{
	u = fnd(u), v = fnd(v);
	if(u==v) u = v = 0;
	if(sz[u]>sz[v]) swap(u,v);
	qu.push_back({u,v});
	par[u] = v;
	sz[v] += sz[u];
	
}
	
void upt(int x)
{
	if(x>M){
		join(0,0);
		join(0,0);
		cnt.push_back(0);
		return;
	}
	if(!x){
		for(int i=0; i<2; i++){
			pii q = qu.back();
			sz[q.vb] -= sz[q.va];
			par[q.va] = q.va;
			qu.pop_back();
		}
		pos -= cnt.back();
		cnt.pop_back();
	}
	else{
		join(E[x].va,E[x].vb+N);
		join(E[x].va+N,E[x].vb);
		if(fnd(E[x].va)==fnd(E[x].va+N)){
			pos++;
			cnt.push_back(1);
		}
		else cnt.push_back(0);
	}
}
	
void solve(int s, int e, int x, int y)
{
	if(s>e) return;
	int m = (s+e)/2;
	int z = y;
	for(int i=s; i<m; i++) upt(i);
	while(1){
		upt(z);
		if(pos||z==m){
			ans[m] = z;
			break;
		}
		z--;
	}
	for(int i=z; i<=y; i++) upt(0);
	for(int i=s; i<m; i++) upt(0);
	
	for(int i=z+1; i<=y; i++) upt(i);	
	solve(s,m-1,x,z);
	for(int i=z+1; i<=y; i++) upt(0);	
	
	for(int i=s; i<=m; i++) upt(i);
	solve(m+1,e,max(m+1,z),y);
	for(int i=s; i<=m; i++) upt(0);
}
	
int main()
{
	ios_base::sync_with_stdio(0),cin.tie(0);
	cin >> N >> M >> Q;
	
	for(int i=1; i<=M; i++) cin >> E[i].va >> E[i].vb;
	
	for(int i=1; i<=2*N; i++){
		par[i] = i;
		sz[i] = 1;
	}
	solve(1,M,1,M+1);
	
	while(Q--){
		int l,r;
		cin >> l >> r;
		cout << (r<ans[l] ? "YES\n" : "NO\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