oj.uz

Submission #331412

# Submission time Handle Problem Language Result Execution time Memory
331412 2020-11-28T11:55:19 Z GioChkhaidze Port Facility (JOI17_port_facility) C++14
100 / 100
 4551 ms 320400 KB 
#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";
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 94316 KB Output is correct
2 Correct 59 ms 94316 KB Output is correct
3 Correct 63 ms 94316 KB Output is correct
4 Correct 59 ms 94444 KB Output is correct
5 Correct 59 ms 94316 KB Output is correct
6 Correct 57 ms 94316 KB Output is correct
7 Correct 57 ms 94316 KB Output is correct
8 Correct 58 ms 94316 KB Output is correct
9 Correct 65 ms 94292 KB Output is correct
10 Correct 58 ms 94444 KB Output is correct
11 Correct 57 ms 94316 KB Output is correct
12 Correct 58 ms 94316 KB Output is correct
13 Correct 59 ms 94316 KB Output is correct
14 Correct 60 ms 94444 KB Output is correct
15 Correct 65 ms 94316 KB Output is correct
16 Correct 58 ms 94444 KB Output is correct
17 Correct 57 ms 94316 KB Output is correct
18 Correct 58 ms 94316 KB Output is correct
19 Correct 60 ms 94316 KB Output is correct
20 Correct 73 ms 94316 KB Output is correct
21 Correct 59 ms 94316 KB Output is correct
22 Correct 56 ms 94316 KB Output is correct
23 Correct 57 ms 94412 KB Output is correct
24 Correct 70 ms 94320 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 94316 KB Output is correct
2 Correct 59 ms 94316 KB Output is correct
3 Correct 63 ms 94316 KB Output is correct
4 Correct 59 ms 94444 KB Output is correct
5 Correct 59 ms 94316 KB Output is correct
6 Correct 57 ms 94316 KB Output is correct
7 Correct 57 ms 94316 KB Output is correct
8 Correct 58 ms 94316 KB Output is correct
9 Correct 65 ms 94292 KB Output is correct
10 Correct 58 ms 94444 KB Output is correct
11 Correct 57 ms 94316 KB Output is correct
12 Correct 58 ms 94316 KB Output is correct
13 Correct 59 ms 94316 KB Output is correct
14 Correct 60 ms 94444 KB Output is correct
15 Correct 65 ms 94316 KB Output is correct
16 Correct 58 ms 94444 KB Output is correct
17 Correct 57 ms 94316 KB Output is correct
18 Correct 58 ms 94316 KB Output is correct
19 Correct 60 ms 94316 KB Output is correct
20 Correct 73 ms 94316 KB Output is correct
21 Correct 59 ms 94316 KB Output is correct
22 Correct 56 ms 94316 KB Output is correct
23 Correct 57 ms 94412 KB Output is correct
24 Correct 70 ms 94320 KB Output is correct
25 Correct 65 ms 94700 KB Output is correct
26 Correct 65 ms 94828 KB Output is correct
27 Correct 60 ms 94572 KB Output is correct
28 Correct 63 ms 94572 KB Output is correct
29 Correct 62 ms 94572 KB Output is correct
30 Correct 68 ms 94572 KB Output is correct
31 Correct 59 ms 94572 KB Output is correct
32 Correct 61 ms 94700 KB Output is correct
33 Correct 58 ms 94572 KB Output is correct
34 Correct 58 ms 94572 KB Output is correct
35 Correct 58 ms 94572 KB Output is correct
36 Correct 67 ms 94700 KB Output is correct
37 Correct 58 ms 94572 KB Output is correct
38 Correct 60 ms 94572 KB Output is correct
39 Correct 60 ms 94572 KB Output is correct
40 Correct 60 ms 94572 KB Output is correct
41 Correct 60 ms 94828 KB Output is correct
42 Correct 58 ms 94700 KB Output is correct
43 Correct 60 ms 94572 KB Output is correct
44 Correct 62 ms 94572 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 94316 KB Output is correct
2 Correct 59 ms 94316 KB Output is correct
3 Correct 63 ms 94316 KB Output is correct
4 Correct 59 ms 94444 KB Output is correct
5 Correct 59 ms 94316 KB Output is correct
6 Correct 57 ms 94316 KB Output is correct
7 Correct 57 ms 94316 KB Output is correct
8 Correct 58 ms 94316 KB Output is correct
9 Correct 65 ms 94292 KB Output is correct
10 Correct 58 ms 94444 KB Output is correct
11 Correct 57 ms 94316 KB Output is correct
12 Correct 58 ms 94316 KB Output is correct
13 Correct 59 ms 94316 KB Output is correct
14 Correct 60 ms 94444 KB Output is correct
15 Correct 65 ms 94316 KB Output is correct
16 Correct 58 ms 94444 KB Output is correct
17 Correct 57 ms 94316 KB Output is correct
18 Correct 58 ms 94316 KB Output is correct
19 Correct 60 ms 94316 KB Output is correct
20 Correct 73 ms 94316 KB Output is correct
21 Correct 59 ms 94316 KB Output is correct
22 Correct 56 ms 94316 KB Output is correct
23 Correct 57 ms 94412 KB Output is correct
24 Correct 70 ms 94320 KB Output is correct
25 Correct 65 ms 94700 KB Output is correct
26 Correct 65 ms 94828 KB Output is correct
27 Correct 60 ms 94572 KB Output is correct
28 Correct 63 ms 94572 KB Output is correct
29 Correct 62 ms 94572 KB Output is correct
30 Correct 68 ms 94572 KB Output is correct
31 Correct 59 ms 94572 KB Output is correct
32 Correct 61 ms 94700 KB Output is correct
33 Correct 58 ms 94572 KB Output is correct
34 Correct 58 ms 94572 KB Output is correct
35 Correct 58 ms 94572 KB Output is correct
36 Correct 67 ms 94700 KB Output is correct
37 Correct 58 ms 94572 KB Output is correct
38 Correct 60 ms 94572 KB Output is correct
39 Correct 60 ms 94572 KB Output is correct
40 Correct 60 ms 94572 KB Output is correct
41 Correct 60 ms 94828 KB Output is correct
42 Correct 58 ms 94700 KB Output is correct
43 Correct 60 ms 94572 KB Output is correct
44 Correct 62 ms 94572 KB Output is correct
45 Correct 315 ms 111072 KB Output is correct
46 Correct 320 ms 111156 KB Output is correct
47 Correct 305 ms 111072 KB Output is correct
48 Correct 325 ms 111072 KB Output is correct
49 Correct 308 ms 111200 KB Output is correct
50 Correct 220 ms 108768 KB Output is correct
51 Correct 271 ms 109920 KB Output is correct
52 Correct 228 ms 107232 KB Output is correct
53 Correct 302 ms 116832 KB Output is correct
54 Correct 188 ms 107360 KB Output is correct
55 Correct 197 ms 107360 KB Output is correct
56 Correct 199 ms 107360 KB Output is correct
57 Correct 250 ms 107488 KB Output is correct
58 Correct 244 ms 107360 KB Output is correct
59 Correct 281 ms 110432 KB Output is correct
60 Correct 284 ms 109920 KB Output is correct
61 Correct 302 ms 110048 KB Output is correct
62 Correct 202 ms 107596 KB Output is correct
63 Correct 214 ms 107360 KB Output is correct
64 Correct 191 ms 107360 KB Output is correct
65 Correct 238 ms 107232 KB Output is correct
66 Correct 228 ms 107360 KB Output is correct
67 Correct 345 ms 112480 KB Output is correct
68 Correct 342 ms 112628 KB Output is correct
69 Correct 335 ms 110944 KB Output is correct
70 Correct 327 ms 110948 KB Output is correct
71 Correct 329 ms 112480 KB Output is correct
72 Correct 311 ms 112480 KB Output is correct
73 Correct 324 ms 112096 KB Output is correct
74 Correct 319 ms 112096 KB Output is correct
75 Correct 264 ms 107360 KB Output is correct
76 Correct 265 ms 107492 KB Output is correct
77 Correct 251 ms 107360 KB Output is correct
78 Correct 326 ms 111072 KB Output is correct
79 Correct 318 ms 111072 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 94316 KB Output is correct
2 Correct 59 ms 94316 KB Output is correct
3 Correct 63 ms 94316 KB Output is correct
4 Correct 59 ms 94444 KB Output is correct
5 Correct 59 ms 94316 KB Output is correct
6 Correct 57 ms 94316 KB Output is correct
7 Correct 57 ms 94316 KB Output is correct
8 Correct 58 ms 94316 KB Output is correct
9 Correct 65 ms 94292 KB Output is correct
10 Correct 58 ms 94444 KB Output is correct
11 Correct 57 ms 94316 KB Output is correct
12 Correct 58 ms 94316 KB Output is correct
13 Correct 59 ms 94316 KB Output is correct
14 Correct 60 ms 94444 KB Output is correct
15 Correct 65 ms 94316 KB Output is correct
16 Correct 58 ms 94444 KB Output is correct
17 Correct 57 ms 94316 KB Output is correct
18 Correct 58 ms 94316 KB Output is correct
19 Correct 60 ms 94316 KB Output is correct
20 Correct 73 ms 94316 KB Output is correct
21 Correct 59 ms 94316 KB Output is correct
22 Correct 56 ms 94316 KB Output is correct
23 Correct 57 ms 94412 KB Output is correct
24 Correct 70 ms 94320 KB Output is correct
25 Correct 65 ms 94700 KB Output is correct
26 Correct 65 ms 94828 KB Output is correct
27 Correct 60 ms 94572 KB Output is correct
28 Correct 63 ms 94572 KB Output is correct
29 Correct 62 ms 94572 KB Output is correct
30 Correct 68 ms 94572 KB Output is correct
31 Correct 59 ms 94572 KB Output is correct
32 Correct 61 ms 94700 KB Output is correct
33 Correct 58 ms 94572 KB Output is correct
34 Correct 58 ms 94572 KB Output is correct
35 Correct 58 ms 94572 KB Output is correct
36 Correct 67 ms 94700 KB Output is correct
37 Correct 58 ms 94572 KB Output is correct
38 Correct 60 ms 94572 KB Output is correct
39 Correct 60 ms 94572 KB Output is correct
40 Correct 60 ms 94572 KB Output is correct
41 Correct 60 ms 94828 KB Output is correct
42 Correct 58 ms 94700 KB Output is correct
43 Correct 60 ms 94572 KB Output is correct
44 Correct 62 ms 94572 KB Output is correct
45 Correct 315 ms 111072 KB Output is correct
46 Correct 320 ms 111156 KB Output is correct
47 Correct 305 ms 111072 KB Output is correct
48 Correct 325 ms 111072 KB Output is correct
49 Correct 308 ms 111200 KB Output is correct
50 Correct 220 ms 108768 KB Output is correct
51 Correct 271 ms 109920 KB Output is correct
52 Correct 228 ms 107232 KB Output is correct
53 Correct 302 ms 116832 KB Output is correct
54 Correct 188 ms 107360 KB Output is correct
55 Correct 197 ms 107360 KB Output is correct
56 Correct 199 ms 107360 KB Output is correct
57 Correct 250 ms 107488 KB Output is correct
58 Correct 244 ms 107360 KB Output is correct
59 Correct 281 ms 110432 KB Output is correct
60 Correct 284 ms 109920 KB Output is correct
61 Correct 302 ms 110048 KB Output is correct
62 Correct 202 ms 107596 KB Output is correct
63 Correct 214 ms 107360 KB Output is correct
64 Correct 191 ms 107360 KB Output is correct
65 Correct 238 ms 107232 KB Output is correct
66 Correct 228 ms 107360 KB Output is correct
67 Correct 345 ms 112480 KB Output is correct
68 Correct 342 ms 112628 KB Output is correct
69 Correct 335 ms 110944 KB Output is correct
70 Correct 327 ms 110948 KB Output is correct
71 Correct 329 ms 112480 KB Output is correct
72 Correct 311 ms 112480 KB Output is correct
73 Correct 324 ms 112096 KB Output is correct
74 Correct 319 ms 112096 KB Output is correct
75 Correct 264 ms 107360 KB Output is correct
76 Correct 265 ms 107492 KB Output is correct
77 Correct 251 ms 107360 KB Output is correct
78 Correct 326 ms 111072 KB Output is correct
79 Correct 318 ms 111072 KB Output is correct
80 Correct 4009 ms 264232 KB Output is correct
81 Correct 3999 ms 263884 KB Output is correct
82 Correct 3986 ms 264272 KB Output is correct
83 Correct 3978 ms 264364 KB Output is correct
84 Correct 3887 ms 264136 KB Output is correct
85 Correct 3013 ms 250700 KB Output is correct
86 Correct 3154 ms 256888 KB Output is correct
87 Correct 2719 ms 226508 KB Output is correct
88 Correct 3523 ms 320400 KB Output is correct
89 Correct 2164 ms 226504 KB Output is correct
90 Correct 2182 ms 226528 KB Output is correct
91 Correct 2166 ms 226632 KB Output is correct
92 Correct 2850 ms 226636 KB Output is correct
93 Correct 2881 ms 226376 KB Output is correct
94 Correct 3494 ms 255296 KB Output is correct
95 Correct 3711 ms 251300 KB Output is correct
96 Correct 3855 ms 253264 KB Output is correct
97 Correct 2680 ms 238448 KB Output is correct
98 Correct 2930 ms 241928 KB Output is correct
99 Correct 2742 ms 232076 KB Output is correct
100 Correct 3146 ms 226568 KB Output is correct
101 Correct 3152 ms 226248 KB Output is correct
102 Correct 4454 ms 277656 KB Output is correct
103 Correct 4551 ms 277324 KB Output is correct
104 Correct 4471 ms 261088 KB Output is correct
105 Correct 4475 ms 261064 KB Output is correct
106 Correct 3942 ms 277336 KB Output is correct
107 Correct 4086 ms 277576 KB Output is correct
108 Correct 3982 ms 274880 KB Output is correct
109 Correct 3892 ms 274504 KB Output is correct
110 Correct 3086 ms 226372 KB Output is correct
111 Correct 3052 ms 226504 KB Output is correct
112 Correct 3047 ms 226504 KB Output is correct
113 Correct 4103 ms 264012 KB Output is correct
114 Correct 4080 ms 264068 KB Output is correct