제출 #331412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
331412		GioChkhaidze	Port Facility (JOI17_port_facility)	C++14	100 / 100	4551 ms	320400 KiB

port_facility

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define F first
#define S second

using namespace std;
 
const int N=1e6+6; 
 
int n,a[N],b[N],p[N],sz[N];
map < int , int > f;

vector < int > s,rec;

set < pair < int , int > > st;
set < int > cW[N],cB[N];
 
ll mod=1e9+7;

int P(int x) {
	if (p[x]==x) return x;
	return p[x]=P(p[x]);
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	cin>>n;	
	for (int i=1; i<=n; i++) {
		cin>>a[i]>>b[i];
		s.pb(a[i]);
		s.pb(b[i]);
		f[a[i]]=i;
		f[b[i]]=i;
		p[i]=i;
		sz[i]=1;
	}

	sort(s.begin(),s.end());
	for (int i=0; i<s.size(); i++) {
		int id=f[s[i]];
		int l=a[id],r=b[id];
		
		if (l==s[i]) {
			rec.clear();
			while (st.size()) {
				int minR=(*st.begin()).F;
				int x=(*st.begin()).S;
				if (minR>r) break;
				st.erase(st.find({minR,x}));
				rec.pb(x);
			}
			
			int cur=id;
			cW[cur].insert(r);

			for (int j=0; j<rec.size(); j++) {
				int x=rec[j];
				
				if (cW[x].size() && (*cW[x].begin())<=r && cB[x].size() && (*cB[x].begin())<=r) {
					cout<<0<<"\n";
					exit(0);
				} 
				
				if (cB[x].size() && (*cB[x].begin())<=r) swap(cW[x],cB[x]);
				if (cW[x].size()+cB[x].size()>cW[cur].size()+cB[cur].size()) swap(cur,x);

				sz[cur]+=sz[x];
				p[x]=cur;
				sz[x]=0;

				for (set < int > :: iterator it=cW[x].begin(); it!=cW[x].end(); it++) 
					cB[cur].insert((*it));
					
				for (set < int > :: iterator it=cB[x].begin(); it!=cB[x].end(); it++) 
					cW[cur].insert((*it));
					
				cW[x].clear();
				cW[x].clear();
				
				if (cB[cur].size() && (*cB[cur].begin())==r) 
					swap(cW[cur],cB[cur]);
			}
			
			int Aa=1e9,Bb=1e9;
			if (cW[cur].size()) Aa=(*cW[cur].begin());			
			if (cB[cur].size()) Bb=(*cB[cur].begin());	
			st.insert({min(Aa,Bb),cur});
		}
			else {
			int C=P(id);
			
			int Aa=1e9,Bb=1e9;
			if (cW[C].size()) Aa=(*cW[C].begin());			
			if (cB[C].size()) Bb=(*cB[C].begin());
			st.erase(st.find({min(Aa,Bb),C}));
			
			if (cW[C].find(r)!=cW[C].end()) cW[C].erase(*cW[C].find(r));		
			if (cB[C].find(r)!=cB[C].end()) cB[C].erase(*cB[C].find(r));
			
			Aa=1e9,Bb=1e9;
			if (cW[C].size()) Aa=(*cW[C].begin());			
			if (cB[C].size()) Bb=(*cB[C].begin());	
			if (min(Aa,Bb)==1e9) continue;
			st.insert({min(Aa,Bb),C});
		}
	}

	ll ans=1;
	for (int i=1; i<=n; i++) 
		if (sz[i]) ans=(ans*2)%mod;
	
	cout<<ans<<"\n";
}

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

port_facility.cpp:27:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   27 | main () {
      |       ^
port_facility.cpp: In function 'int main()':
port_facility.cpp:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for (int i=0; i<s.size(); i++) {
      |                ~^~~~~~~~~
port_facility.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    for (int j=0; j<rec.size(); j++) {
      |                  ~^~~~~~~~~~~

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