제출 #131674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
131674		onjo0127	Port Facility (JOI17_port_facility)	C++11	100 / 100	4466 ms	276508 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const int MOD = 1e9 + 7, INF = 1e9;
int N, A[1000009], B[1000009], C[1000009];
pii LA[2000009], RA[2000009];

struct segtree {
	vector<pii> T;
	void init(pii A[], int idx, int s, int e) {
		if(s == e) {
			T[idx] = A[s];
			return;
		}
		int m = s+e >> 1;
		init(A, idx<<1, s, m);
		init(A, idx<<1|1, m+1, e);
		T[idx] = max(T[idx<<1], T[idx<<1|1]);
	}
	void upd(int idx, int s, int e, int p, pii v) {
		if(p < s || e < p) return;
		if(s == e) {
			T[idx] = v;
			return;
		}
		int m = s+e >> 1;
		upd(idx<<1, s, m, p, v);
		upd(idx<<1|1, m+1, e, p, v);
		T[idx] = max(T[idx<<1], T[idx<<1|1]);
	}
	pii get(int idx, int s, int e, int l, int r) {
		if(r < s || e < l) return {-INF, -1};
		if(l <= s && e <= r) return T[idx];
		int m = s+e >> 1;
		return max(get(idx*2, s, m, l, r), get(idx*2+1, m+1, e, l, r));
	}
} LS, RS;

void dfs(int x, int c) {
	C[x] = c;
	RS.upd(1, 1, 2*N, A[x], {-INF, x});
	LS.upd(1, 1, 2*N, B[x], {-INF, x});
	while(1) {
		int lm, rm, id; tie(rm, id) = RS.get(1, 1, 2*N, A[x] + 1, B[x] - 1);
		if(rm > B[x]) {
			dfs(id, 3 - c);
			continue;
		}
		tie(lm, id) = LS.get(1, 1, 2*N, A[x] + 1, B[x] - 1); lm = -lm;
		if(lm < A[x]) {
			dfs(id, 3 - c);
			continue;
		}
		break;
	}
}

bool chk(vector<pii> &S) {
	sort(S.begin(), S.end());
	vector<int> T;
	for(auto& it: S) {
		while(T.size() && T.back() < it.first) T.pop_back();
		if(T.size() && T.back() < it.second) return false;
		T.push_back(it.second);
	}
	return true;
}

int main() {
	LS.T.resize(4200000);
	RS.T.resize(4200000);
	scanf("%d",&N);
	for(int i=1; i<=2*N; i++) LA[i] = RA[i] = {-INF, -1};
	for(int i=1; i<=N; i++) {
		scanf("%d%d",&A[i],&B[i]);
		RA[A[i]] = {B[i], i};
		LA[B[i]] = {-A[i], i};
	}
	LS.init(LA, 1, 1, 2*N); RS.init(RA, 1, 1, 2*N);
	int ans = 1;
	for(int i=1; i<=N; i++) if(!C[i]) {
		dfs(i, 1);
		ans *= 2; ans %= MOD;
	}
	vector<pii> AS, BS;
	for(int i=1; i<=N; i++) {
		if(C[i] == 1) AS.push_back({A[i], B[i]});
		if(C[i] == 2) BS.push_back({A[i], B[i]});
	}
	if(!chk(AS) || !chk(BS)) return !printf("0");
	printf("%d", ans);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

port_facility.cpp: In member function 'void segtree::init(pii*, int, int, int)':
port_facility.cpp:16:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
port_facility.cpp: In member function 'void segtree::upd(int, int, int, int, pii)':
port_facility.cpp:27:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
port_facility.cpp: In member function 'pii segtree::get(int, int, int, int, int)':
port_facility.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
port_facility.cpp: In function 'int main()':
port_facility.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
port_facility.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&A[i],&B[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

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