oj.uz

Submission #257389

# Submission time Handle Problem Language Result Execution time Memory
257389 2020-08-04T08:13:23 Z easrui Joker (BOI20_joker) C++17
0 / 100
 5 ms 640 KB 
#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(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){
			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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -