Submission #213212

#	Time	Username	Problem	Language	Result	Execution time	Memory
213212		patrikpavic2	Port Facility (JOI17_port_facility)	C++17	100 / 100	2595 ms	201644 KiB

port_facility

#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>

#define PB push_back
#define X first
#define Y second

using namespace std;

typedef pair < int, int > pii;

const int N = 2e6 + 500;
const int MOD = 1e9 + 7;

vector < pii > v[N];
int col[N], bio[N], mog = 1, n;
int L[N], R[N], id[N], str[N];
int ima[N], stvar[N];

void dodaj(int x,int y,int razl = 1){
	//printf("%d --%d-- %d\n", x, razl, y);
	v[x].PB({y, razl});
	v[y].PB({x, razl});
}

void dfs(int x){
	if(bio[x]) return;
	bio[x] = 1;
	for(pii nxt : v[x]){
		if(bio[nxt.X] && (col[x] ^ col[nxt.X]) != nxt.Y)
			mog = 0;
		if(!bio[nxt.X]){
			col[nxt.X] = col[x] ^ nxt.Y;
			dfs(nxt.X);
		}
	}
}

inline bool inter(int i,int j){
	if(i == j) return 0;
	if(L[i] < L[j] && R[i] < R[j] && R[i] > L[j])
		return 1;
	if(L[i] > L[j] && R[i] > R[j] && R[j] > L[i])
		return 1;
	return 0;
}

void obradi(int l,int r){
	if(l >= r) return;
	//printf("l = %d r = %d\n", l, r);
	int mid = (l + r) / 2;
	int lst = -1, cnt = 0, pos = 0;
	vector < int > sljed;
	// RIJESI SVE PREMA DESNO
	for(int i = mid + 1;i <= r;i++){
		if(L[id[i]] < l || R[id[i]] > r) continue;
		if(str[i]){
			if(L[id[i]] <= mid){				
				if(lst != -1 && cnt)
					dodaj(id[i], lst, 0);
				lst = id[i];
				for(int x : sljed){
					if(inter(lst, x))
						dodaj(lst, x, 1);
				}
				sljed.clear();
				cnt += pos; pos = 0;
			}
			else if(lst == -1 || L[id[i]] > R[lst])
				pos--;
			else
				cnt--;
		}
		else{
			sljed.PB(id[i]);
			pos++;
		}
		//printf("cnt = %d pos = %d i = %d\n", cnt, pos, i);
	}
	//printf("rijesio desno\n");
	lst = -1, cnt = 0, pos = 0;
	sljed.clear();
	// RIJESI SVE PREMA LIJEVO
	for(int i = mid;i >= l;i--){
		if(L[id[i]] < l || R[id[i]] > r) continue;
		if(!str[i]){
			if(R[id[i]] > mid){
				if(lst != -1 && cnt)
					dodaj(id[i], lst, 0);
				lst = id[i];
				for(int x : sljed){
					if(inter(lst, x))
						dodaj(lst, x, 1);
				}
				sljed.clear();
				cnt += pos; pos = 0;
			}
			else if(lst == -1 || R[id[i]] < L[lst])
				pos--;
			else
				cnt--;
		}
		else{
			sljed.PB(id[i]);
			pos++;
		}
	}
	//printf("rijesio lijevo\n");
	// RIJESI SVE KOJI SIJEKU
	vector < int > niz;
	for(int i = l;i <= mid;i++){
		if(L[id[i]] < l || R[id[i]] > r) continue;
		if(R[id[i]] > mid){
			niz.PB(id[i]);
		}
	}
	int cur = (int)niz.size();
	for(int i = mid + 1;i <= r;i++){
		if(L[id[i]] < l || R[id[i]] > r) continue;
		if(L[id[i]] <= mid)
			stvar[id[i]] = cur--;	
	}
	stack < int > svi;
	int zad = 1;int mx = -1;
	for(int x : niz){
		//printf("x = %d stvar[ %d ] = %d\n", x, x, stvar[x]);
		if(mx != -1 && stvar[mx] > zad && stvar[x] > zad)
			dodaj(mx, x, 0);
		if(mx == -1 || stvar[x] > stvar[mx]){ 
			mx = x;
		}
		if(mx != x)
			dodaj(x, mx, 1);
		ima[stvar[x]]++;
		while(ima[zad]) 
			zad++;
		//while(!svi.empty() && stvar[svi.top()] < stvar[x]){
		//	if(stvar[svi.top()] > zad && stvar[x] > zad)
		//		dodaj(svi.top(), x, 0);
		//	svi.pop();
		//}
		//svi.push(x);
	}
	//printf("rijesio sredinu\n");
	for(int i = 0;i <= (int)niz.size();i++)
		ima[i] = 0;
	obradi(l, mid); obradi(mid + 1, r);
}


int main(){
	scanf("%d", &n);
	for(int i = 1;i <= n;i++){
		scanf("%d%d", L + i, R + i);
		id[L[i]] = i, id[R[i]] = i;
		str[R[i]] = 1;
	}
	obradi(1, 2 * n);
	int komp = 0;
	for(int i = 1;i <= n;i++){
		komp += !bio[i]; dfs(i);
	}
	int sol = 1;
	for(;komp--;) sol = (sol + sol) % MOD;
	printf("%d\n", sol * mog);
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:154:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
port_facility.cpp:156:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", L + i, R + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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