Submission #105834

#	Time	Username	Problem	Language	Result	Execution time	Memory
105834		Pro_ktmr	Port Facility (JOI17_port_facility)	C++14	22 / 100	6157 ms	961864 KiB

port_facility

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define MP(a,b) make_pair(a,b)
#define MOD 1000000007LL
int N;
vector<pair<int,int> > v;
int A[1000000],B[1000000];
vector<int> betsu[1000000];
int group[1000000];
int main(){
	scanf("%d", &N);
	if(N > 100000) return -1;
	for(int i=0; i<N; i++){
		int a,b;
		scanf("%d%d", &a, &b);
		a--; b--;
		v.push_back(MP(a,b));
	}
	
	sort(v.begin(), v.end());
	for(int i=0; i<N; i++){
		A[i] = v[i].first;
		B[i] = v[i].second;
		group[i] = -1;
	}
	
	set<pair<int,int> > st;
	for(int i=0; i<N; i++){
		while(st.size() > 0 && st.begin()->first < A[i]) st.erase(st.begin());
		auto itr = st.lower_bound(MP(B[i],0));
		while(itr != st.begin()){
			itr--;
			betsu[i].push_back(itr->second);
			betsu[itr->second].push_back(i);
		}
		st.insert(MP(B[i],i));
	}
	
	LL ans = 1;
	for(int i=0; i<N; i++){
		if(group[i] != -1) continue;
		ans *= 2;
		ans %= MOD;
		group[i] = 0;
		queue<int> que;
		que.push(i);
		while(!que.empty()){
			int now = que.front();
			que.pop();
			for(int j=0; j<betsu[now].size(); j++){
				if(group[betsu[now][j]] == -1){
					group[betsu[now][j]] = (group[now]+1) % 2;
					que.push(betsu[now][j]);
				}
				else if(group[betsu[now][j]] == group[now]){
					ans = 0;
					printf("%d\n", ans);
					return 0;
				}
			}
		}
	}
	printf("%d\n", ans);
	
	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:51:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<betsu[now].size(); j++){
                 ~^~~~~~~~~~~~~~~~~~
port_facility.cpp:58:24: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
      printf("%d\n", ans);
                        ^
port_facility.cpp:64:20: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  printf("%d\n", ans);
                    ^
port_facility.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
port_facility.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

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