Submission #573411

#	Time	Username	Problem	Language	Result	Execution time	Memory
573411		amunduzbaev	Joker (BOI20_joker)	C++17	100 / 100	609 ms	34416 KiB

Joker

#include "bits/stdc++.h"
using namespace std;

#define ar array
#define int long long

const int N = 2e5 + 5;
vector<int> edges[N];
int sz[N], par[N], c[N], is[N], R[N];
ar<int, 2> e[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m, q; cin>>n>>m>>q;
	for(int i=1;i<=m;i++){
		cin>>e[i][0]>>e[i][1];
		edges[e[i][0]].push_back(e[i][1]);
		edges[e[i][1]].push_back(e[i][0]);
	}
	
	for(int i=0;i<N;i++) sz[i] = 1, par[i] = i;
	function<ar<int, 2>(int)> f = [&](int x) -> ar<int, 2>{
		if(par[x ] == x) return {x, c[x]};
		auto t = f(par[x]);
		return {t[0], t[1] ^ c[x]};
	};
	int cnt = 0;
	vector<ar<int, 3>> last;
	auto merge = [&](int a, int b){
		//~ cout<<a<<" "<<b<<"\n";
		auto ax = f(a), bx = f(b);
		a = ax[0], b = bx[0];
		//~ cout<<a<<" "<<b<<"\n";
		if(a == b){
			cnt += (ax[1] == bx[1]);
			return;
		}
		if(sz[a] < sz[b]) swap(a, b);
		int is = 0;
		if(ax[1] == bx[1]) is = 1;
		par[b] = a, sz[a] += sz[b];
		c[b] ^= is;
		last.push_back({a, b, is});
	};
	
	auto roll_back = [&](int m){
		while((int)last.size() > m){
			auto x = last.back(); last.pop_back();
			par[x[1]] = x[1], sz[x[0]] -= sz[x[1]];
			c[x[1]] ^= x[2];
		}
	};
	
	auto add = [&](int x){
		merge(e[x][0], e[x][1]);
	};
	
	function<void(int, int, int, int)> dnc = [&](int l, int r, int lx, int rx){
		//~ cout<<l<<" "<<r<<endl;
		if(l > r) return;
		assert(lx <= rx);
		int m = (l + r) >> 1;
		int sz = last.size(), cc = cnt;
		for(int x=l;x<m;x++) add(x);
		int x = rx;
		while(!cnt && x >= m){
			add(x);
			x--;
		}
		R[m] = x;
		//~ cout<<m<<" "<<x<<"\n";
		
		roll_back(sz), cnt = cc;
		for(int x=rx;x>R[m];x--) add(x);
		dnc(l, m - 1, lx, R[m]);
		roll_back(sz), cnt = cc;
		for(int x=l;x<=m;x++) add(x);
		dnc(m + 1, r, R[m], rx);
		roll_back(sz), cnt = cc;
	};
	
	dnc(1, m, 1, m);
	//~ for(int i=1;i<=n;i++) cout<<R[i]<<" ";
	//~ cout<<"\n";
	
	while(q--){
		int l, r; cin>>l>>r;
		if(r <= R[l]) cout<<"YES\n";
		else cout<<"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