Submission #1282071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282071		PlayVoltz	Port Facility (JOI17_port_facility)	C++20	100 / 100	983 ms	360648 KiB

port_facility

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
#include <random>
using namespace std;

#define int long long
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

const int MOD = 1000000007;

vector<pii> dsu;

pii nmerge(pii a, pii b){
	if (!a.fi)return b;
	if (!b.fi)return a;
	if (a==b)return a;
	return mp(-1, 0);
}

pii fp(int a){
	if (dsu[a].fi==-1)return mp(a, dsu[a].se);
	pii res=fp(dsu[a].fi);
	return dsu[a]=mp(res.fi, res.se^dsu[a].se);
}

void merge(pii a, pii b){
	bool temp=a.se;
	a=fp(a.fi);
	if (a.fi==b.fi){
		if ((temp^a.se)==b.se)cout<<0, exit(0);
		return;
	}
	dsu[a.fi].fi=b.fi;
	dsu[a.fi].se=a.se^temp^1;
}

struct node{
	int s, e, m;
	pii val, lazy;
	node *l, *r;
	void create(){
		if (l==nullptr){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void propagate(){
		if (!lazy.fi)return;
		if (val.fi)val=lazy;
		if (s!=e){
			create();
			l->lazy=lazy;
			r->lazy=lazy;
		}
		lazy=mp(0, 0);
	}
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		val=lazy=mp(0, 0);
		l=r=nullptr;
	}
	void up(int id, pii v){
		propagate();
		if (s==e)val=v;
		else{
			create();
			if (id<=m)l->up(id, v);
			else r->up(id, v);
			r->propagate(), l->propagate();
			val=nmerge(l->val, r->val);
		}
		
	}
	void query(int left, int right, int i){
		propagate();
		if (!val.fi)return;
		if (s==left&&e==right&&val.fi!=-1){
			merge(val, mp(i, 0));
			lazy=mp(i, 1);
			return;
		}
		create();
		if (right<=m)l->query(left, right, i);
		else if (left>m)r->query(left, right, i);
		else l->query(left, m, i), r->query(m+1, right, i);
		l->propagate(), r->propagate();
		val=nmerge(l->val, r->val);
	}
}*st;

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, ans=1;
	cin>>n;
	vector<pii> vect(n+1);
	for (int i=1; i<=n; ++i)cin>>vect[i].fi>>vect[i].se;
	sort(vect.begin()+1, vect.end());
	dsu.resize(n+1, mp(-1, 0));
	st = new node(1, 2*n);
	for (int i=1; i<=n; ++i)st->query(vect[i].fi, vect[i].se, i), st->up(vect[i].se, mp(i, 0));
	for (int i=1; i<=n; ++i)if (dsu[i].fi==-1)ans=(ans*2)%MOD;
	cout<<ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 22 / 22