Submission #1225105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225105		salmon	Port Facility (JOI17_port_facility)	C++20	0 / 100	0 ms	320 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;

int N;
int lst[2100100];
int A[1100100];
int B[1100100];

int pre[2100100];

		vector<set<int>> Bs;
		vector<int> As;
		

int main(){
	
	scanf(" %d",&N);
	
	for(int i = 1; i <= N * 2; i++){
		lst[i] = -1;
		pre[i] = 0;
	}
	
	for(int i = 0; i < N; i++){
		scanf("%d",&A[i]);
		scanf(" %d",&B[i]);
		lst[A[i]] = B[i];
		lst[B[i]] = A[i];
		
		pre[A[i]]++;
		pre[B[i]]--;
	}
	
	for(int i = 2; i <= N * 2; i++){
		pre[i] += pre[i - 1];
		if(pre[i] >= 3){
			printf("0\n");
			return 0;
		}
	}
	
	int ways = 1;
	
	for(int i = 1; i <= N; i++){

		
		if(Bs.empty()){
			Bs.push_back({lst[i]});
			As.push_back(i);
		}
		else{
			
			while(!Bs.back().empty() && *(Bs.back().begin()) <= i){
				Bs.erase(Bs.begin());
			}
			
			if(Bs.back().empty()){
				ways *= 2;
				Bs.pop_back();
				As.pop_back();
			}
			
			
			if(lst[i] > i){
				if(!Bs.empty()){
					if(*(Bs.back().begin()) > lst[i]){
						Bs.push_back({lst[i]});
						As.push_back(i);
					}
					else{
						set<int>& s1 = Bs.back();
						
						s1.insert(lst[i]);
						
						Bs.pop_back();
						As.pop_back();
						
						while(!Bs.empty() && *(Bs.back().begin()) < lst[i]){
							set<int>& s2 = Bs.back();
							
							if(s1.size() < s2.size()) swap(s1,s2);
							
							for(int i : s2) s1.insert(i);
							
							Bs.pop_back();
							As.pop_back();
						}
						
						As.push_back(i);
						Bs.push_back(s1);
					}
				}
				
				
			}
			
		}
	}
	
	for(set<int>& _ : Bs)ways *= 2;
	
	printf("%d\n",ways);
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
port_facility.cpp:25:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |                 scanf("%d",&A[i]);
      |                 ~~~~~^~~~~~~~~~~~
port_facility.cpp:26:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |                 scanf(" %d",&B[i]);
      |                 ~~~~~^~~~~~~~~~~~~

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