oj.uz

Submission #132109

# Submission time Handle Problem Language Result Execution time Memory
132109 2019-07-18T10:08:08 Z shayan_p Port Facility (JOI17_port_facility) C++14
100 / 100
 3332 ms 414816 KB 
// only miss the sun when it starts to snow

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=2e6+10,mod=1e9+7;
const ll inf=1e18;

int par[maxn], who[maxn], n;
bool st[maxn], bad=0;
vector<int> v[4*maxn];

pair<int,bool> Find(int u){
    if(par[u]<0) return {u,0};
    pair<int,bool> a= Find(par[u]);
    a.S^= st[u];
    par[u]= a.F, st[u]= a.S;

    return {par[u],st[u]};
}
void Merge(int a,int b){
    if(a==b) return;
    pair<int,bool> A=Find(a), B=Find(b);

    if(A.F == B.F){
	bad|= A.S==B.S;
	return;
    }
    if( par[A.F] > par[B.F] ) swap(A,B);

    par[A.F]+=par[B.F];
    par[B.F]= A.F;
    st[B.F]= A.S ^ B.S ^ 1;
}

void build(int l=0,int r=maxn, int id=1){
    if(r-l==1){
	if(who[l] != 0)	v[id].PB( who[l] );
	return;
    }
    int mid=(l+r)>>1;
    build(l,mid,2*id);
    build(mid,r,2*id+1);
    v[id].resize( sz(v[2*id]) + sz(v[2*id+1]) );
    merge( v[2*id].begin(), v[2*id].end(), v[2*id+1].begin(), v[2*id+1].end(), v[id].begin() );
}
void mrg(int f,int s,int l=0,int r=maxn,int id=1){
    if(f>=s || l>=r|| s<=l || r<=f) return;
    if(f<=l && r<=s){
	int mx=-1;
	while(sz(v[id]) && s<v[id].back() ) Merge(v[id].back(), s), mx=max(mx, v[id].back() ), v[id].pop_back();
	if(mx!=-1) v[id].PB(mx);
	return;
    }
    int mid=(l+r)>>1;
    mrg(f,s,l,mid,2*id), mrg(f,s,mid,r,2*id+1);
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);

    memset(par,-1,sizeof par);

    cin>>n;

    for(int i=0;i<n;i++){
	int a,b; cin>>a>>b;
	who[a]= b;
    }

    build();

    for(int i=1;i<=2*n;i++){
	if(who[i]!=0){
	    mrg(i,who[i]);
	}
    }
    if(bad) return cout<<0<<endl,0;

    set<int> st;

    for(int i=1;i<=2*n;i++){
	if(who[i]!=0){
	    st.insert(Find(who[i]).F);
	}
    }
    int ans=1;
    for(int i=0;i<sz(st);i++)
	ans=2ll*ans %mod;
    return cout<<ans<<endl,0;
}
// Deathly mistakes:
//  * Read the problem curfully.
//  * Check maxn.
//  * Overflows.


// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 196088 KB Output is correct
2 Correct 208 ms 196216 KB Output is correct
3 Correct 210 ms 196124 KB Output is correct
4 Correct 224 ms 196088 KB Output is correct
5 Correct 226 ms 196004 KB Output is correct
6 Correct 217 ms 196096 KB Output is correct
7 Correct 208 ms 196180 KB Output is correct
8 Correct 207 ms 196060 KB Output is correct
9 Correct 220 ms 196048 KB Output is correct
10 Correct 221 ms 196248 KB Output is correct
11 Correct 229 ms 196080 KB Output is correct
12 Correct 217 ms 196264 KB Output is correct
13 Correct 236 ms 196216 KB Output is correct
14 Correct 235 ms 196088 KB Output is correct
15 Correct 221 ms 196088 KB Output is correct
16 Correct 209 ms 196216 KB Output is correct
17 Correct 208 ms 196084 KB Output is correct
18 Correct 211 ms 196016 KB Output is correct
19 Correct 211 ms 196184 KB Output is correct
20 Correct 214 ms 196124 KB Output is correct
21 Correct 207 ms 196092 KB Output is correct
22 Correct 213 ms 196032 KB Output is correct
23 Correct 209 ms 196112 KB Output is correct
24 Correct 207 ms 196188 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 196088 KB Output is correct
2 Correct 208 ms 196216 KB Output is correct
3 Correct 210 ms 196124 KB Output is correct
4 Correct 224 ms 196088 KB Output is correct
5 Correct 226 ms 196004 KB Output is correct
6 Correct 217 ms 196096 KB Output is correct
7 Correct 208 ms 196180 KB Output is correct
8 Correct 207 ms 196060 KB Output is correct
9 Correct 220 ms 196048 KB Output is correct
10 Correct 221 ms 196248 KB Output is correct
11 Correct 229 ms 196080 KB Output is correct
12 Correct 217 ms 196264 KB Output is correct
13 Correct 236 ms 196216 KB Output is correct
14 Correct 235 ms 196088 KB Output is correct
15 Correct 221 ms 196088 KB Output is correct
16 Correct 209 ms 196216 KB Output is correct
17 Correct 208 ms 196084 KB Output is correct
18 Correct 211 ms 196016 KB Output is correct
19 Correct 211 ms 196184 KB Output is correct
20 Correct 214 ms 196124 KB Output is correct
21 Correct 207 ms 196092 KB Output is correct
22 Correct 213 ms 196032 KB Output is correct
23 Correct 209 ms 196112 KB Output is correct
24 Correct 207 ms 196188 KB Output is correct
25 Correct 213 ms 196448 KB Output is correct
26 Correct 215 ms 196512 KB Output is correct
27 Correct 212 ms 196368 KB Output is correct
28 Correct 246 ms 196528 KB Output is correct
29 Correct 224 ms 196600 KB Output is correct
30 Correct 210 ms 196444 KB Output is correct
31 Correct 217 ms 196456 KB Output is correct
32 Correct 210 ms 196344 KB Output is correct
33 Correct 239 ms 196472 KB Output is correct
34 Correct 249 ms 196392 KB Output is correct
35 Correct 212 ms 196472 KB Output is correct
36 Correct 212 ms 196472 KB Output is correct
37 Correct 212 ms 196396 KB Output is correct
38 Correct 219 ms 196384 KB Output is correct
39 Correct 212 ms 196600 KB Output is correct
40 Correct 213 ms 196528 KB Output is correct
41 Correct 211 ms 196344 KB Output is correct
42 Correct 209 ms 196348 KB Output is correct
43 Correct 227 ms 196472 KB Output is correct
44 Correct 211 ms 196472 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 196088 KB Output is correct
2 Correct 208 ms 196216 KB Output is correct
3 Correct 210 ms 196124 KB Output is correct
4 Correct 224 ms 196088 KB Output is correct
5 Correct 226 ms 196004 KB Output is correct
6 Correct 217 ms 196096 KB Output is correct
7 Correct 208 ms 196180 KB Output is correct
8 Correct 207 ms 196060 KB Output is correct
9 Correct 220 ms 196048 KB Output is correct
10 Correct 221 ms 196248 KB Output is correct
11 Correct 229 ms 196080 KB Output is correct
12 Correct 217 ms 196264 KB Output is correct
13 Correct 236 ms 196216 KB Output is correct
14 Correct 235 ms 196088 KB Output is correct
15 Correct 221 ms 196088 KB Output is correct
16 Correct 209 ms 196216 KB Output is correct
17 Correct 208 ms 196084 KB Output is correct
18 Correct 211 ms 196016 KB Output is correct
19 Correct 211 ms 196184 KB Output is correct
20 Correct 214 ms 196124 KB Output is correct
21 Correct 207 ms 196092 KB Output is correct
22 Correct 213 ms 196032 KB Output is correct
23 Correct 209 ms 196112 KB Output is correct
24 Correct 207 ms 196188 KB Output is correct
25 Correct 213 ms 196448 KB Output is correct
26 Correct 215 ms 196512 KB Output is correct
27 Correct 212 ms 196368 KB Output is correct
28 Correct 246 ms 196528 KB Output is correct
29 Correct 224 ms 196600 KB Output is correct
30 Correct 210 ms 196444 KB Output is correct
31 Correct 217 ms 196456 KB Output is correct
32 Correct 210 ms 196344 KB Output is correct
33 Correct 239 ms 196472 KB Output is correct
34 Correct 249 ms 196392 KB Output is correct
35 Correct 212 ms 196472 KB Output is correct
36 Correct 212 ms 196472 KB Output is correct
37 Correct 212 ms 196396 KB Output is correct
38 Correct 219 ms 196384 KB Output is correct
39 Correct 212 ms 196600 KB Output is correct
40 Correct 213 ms 196528 KB Output is correct
41 Correct 211 ms 196344 KB Output is correct
42 Correct 209 ms 196348 KB Output is correct
43 Correct 227 ms 196472 KB Output is correct
44 Correct 211 ms 196472 KB Output is correct
45 Correct 348 ms 214004 KB Output is correct
46 Correct 348 ms 213980 KB Output is correct
47 Correct 376 ms 213952 KB Output is correct
48 Correct 344 ms 214040 KB Output is correct
49 Correct 360 ms 214000 KB Output is correct
50 Correct 334 ms 213016 KB Output is correct
51 Correct 370 ms 213084 KB Output is correct
52 Correct 344 ms 219128 KB Output is correct
53 Correct 368 ms 215928 KB Output is correct
54 Correct 355 ms 211176 KB Output is correct
55 Correct 348 ms 211240 KB Output is correct
56 Correct 428 ms 211200 KB Output is correct
57 Correct 360 ms 216024 KB Output is correct
58 Correct 343 ms 218156 KB Output is correct
59 Correct 355 ms 217732 KB Output is correct
60 Correct 347 ms 215744 KB Output is correct
61 Correct 348 ms 214380 KB Output is correct
62 Correct 327 ms 213548 KB Output is correct
63 Correct 333 ms 213120 KB Output is correct
64 Correct 336 ms 212972 KB Output is correct
65 Correct 427 ms 212252 KB Output is correct
66 Correct 419 ms 212368 KB Output is correct
67 Correct 346 ms 212376 KB Output is correct
68 Correct 345 ms 212404 KB Output is correct
69 Correct 345 ms 211996 KB Output is correct
70 Correct 342 ms 211960 KB Output is correct
71 Correct 325 ms 211168 KB Output is correct
72 Correct 325 ms 211196 KB Output is correct
73 Correct 326 ms 211308 KB Output is correct
74 Correct 327 ms 211192 KB Output is correct
75 Correct 323 ms 214392 KB Output is correct
76 Correct 321 ms 214368 KB Output is correct
77 Correct 329 ms 214508 KB Output is correct
78 Correct 343 ms 213880 KB Output is correct
79 Correct 351 ms 213972 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 196088 KB Output is correct
2 Correct 208 ms 196216 KB Output is correct
3 Correct 210 ms 196124 KB Output is correct
4 Correct 224 ms 196088 KB Output is correct
5 Correct 226 ms 196004 KB Output is correct
6 Correct 217 ms 196096 KB Output is correct
7 Correct 208 ms 196180 KB Output is correct
8 Correct 207 ms 196060 KB Output is correct
9 Correct 220 ms 196048 KB Output is correct
10 Correct 221 ms 196248 KB Output is correct
11 Correct 229 ms 196080 KB Output is correct
12 Correct 217 ms 196264 KB Output is correct
13 Correct 236 ms 196216 KB Output is correct
14 Correct 235 ms 196088 KB Output is correct
15 Correct 221 ms 196088 KB Output is correct
16 Correct 209 ms 196216 KB Output is correct
17 Correct 208 ms 196084 KB Output is correct
18 Correct 211 ms 196016 KB Output is correct
19 Correct 211 ms 196184 KB Output is correct
20 Correct 214 ms 196124 KB Output is correct
21 Correct 207 ms 196092 KB Output is correct
22 Correct 213 ms 196032 KB Output is correct
23 Correct 209 ms 196112 KB Output is correct
24 Correct 207 ms 196188 KB Output is correct
25 Correct 213 ms 196448 KB Output is correct
26 Correct 215 ms 196512 KB Output is correct
27 Correct 212 ms 196368 KB Output is correct
28 Correct 246 ms 196528 KB Output is correct
29 Correct 224 ms 196600 KB Output is correct
30 Correct 210 ms 196444 KB Output is correct
31 Correct 217 ms 196456 KB Output is correct
32 Correct 210 ms 196344 KB Output is correct
33 Correct 239 ms 196472 KB Output is correct
34 Correct 249 ms 196392 KB Output is correct
35 Correct 212 ms 196472 KB Output is correct
36 Correct 212 ms 196472 KB Output is correct
37 Correct 212 ms 196396 KB Output is correct
38 Correct 219 ms 196384 KB Output is correct
39 Correct 212 ms 196600 KB Output is correct
40 Correct 213 ms 196528 KB Output is correct
41 Correct 211 ms 196344 KB Output is correct
42 Correct 209 ms 196348 KB Output is correct
43 Correct 227 ms 196472 KB Output is correct
44 Correct 211 ms 196472 KB Output is correct
45 Correct 348 ms 214004 KB Output is correct
46 Correct 348 ms 213980 KB Output is correct
47 Correct 376 ms 213952 KB Output is correct
48 Correct 344 ms 214040 KB Output is correct
49 Correct 360 ms 214000 KB Output is correct
50 Correct 334 ms 213016 KB Output is correct
51 Correct 370 ms 213084 KB Output is correct
52 Correct 344 ms 219128 KB Output is correct
53 Correct 368 ms 215928 KB Output is correct
54 Correct 355 ms 211176 KB Output is correct
55 Correct 348 ms 211240 KB Output is correct
56 Correct 428 ms 211200 KB Output is correct
57 Correct 360 ms 216024 KB Output is correct
58 Correct 343 ms 218156 KB Output is correct
59 Correct 355 ms 217732 KB Output is correct
60 Correct 347 ms 215744 KB Output is correct
61 Correct 348 ms 214380 KB Output is correct
62 Correct 327 ms 213548 KB Output is correct
63 Correct 333 ms 213120 KB Output is correct
64 Correct 336 ms 212972 KB Output is correct
65 Correct 427 ms 212252 KB Output is correct
66 Correct 419 ms 212368 KB Output is correct
67 Correct 346 ms 212376 KB Output is correct
68 Correct 345 ms 212404 KB Output is correct
69 Correct 345 ms 211996 KB Output is correct
70 Correct 342 ms 211960 KB Output is correct
71 Correct 325 ms 211168 KB Output is correct
72 Correct 325 ms 211196 KB Output is correct
73 Correct 326 ms 211308 KB Output is correct
74 Correct 327 ms 211192 KB Output is correct
75 Correct 323 ms 214392 KB Output is correct
76 Correct 321 ms 214368 KB Output is correct
77 Correct 329 ms 214508 KB Output is correct
78 Correct 343 ms 213880 KB Output is correct
79 Correct 351 ms 213972 KB Output is correct
80 Correct 1864 ms 368048 KB Output is correct
81 Correct 1845 ms 365540 KB Output is correct
82 Correct 1833 ms 365788 KB Output is correct
83 Correct 1808 ms 365776 KB Output is correct
84 Correct 1842 ms 365800 KB Output is correct
85 Correct 1740 ms 355568 KB Output is correct
86 Correct 1732 ms 355848 KB Output is correct
87 Correct 1956 ms 414816 KB Output is correct
88 Correct 1923 ms 383588 KB Output is correct
89 Correct 1915 ms 337644 KB Output is correct
90 Correct 1806 ms 337620 KB Output is correct
91 Correct 1809 ms 337564 KB Output is correct
92 Correct 1758 ms 385764 KB Output is correct
93 Correct 2057 ms 407368 KB Output is correct
94 Correct 1808 ms 395768 KB Output is correct
95 Correct 1776 ms 372856 KB Output is correct
96 Correct 1752 ms 366588 KB Output is correct
97 Correct 1560 ms 359288 KB Output is correct
98 Correct 1607 ms 356560 KB Output is correct
99 Correct 1612 ms 355964 KB Output is correct
100 Correct 3255 ms 349108 KB Output is correct
101 Correct 3332 ms 349404 KB Output is correct
102 Correct 1815 ms 349624 KB Output is correct
103 Correct 1782 ms 349628 KB Output is correct
104 Correct 1849 ms 346728 KB Output is correct
105 Correct 1813 ms 346720 KB Output is correct
106 Correct 1514 ms 338188 KB Output is correct
107 Correct 1533 ms 338180 KB Output is correct
108 Correct 1546 ms 338320 KB Output is correct
109 Correct 1543 ms 338180 KB Output is correct
110 Correct 1467 ms 370560 KB Output is correct
111 Correct 1501 ms 370668 KB Output is correct
112 Correct 1454 ms 370628 KB Output is correct
113 Correct 1865 ms 366616 KB Output is correct
114 Correct 1828 ms 366444 KB Output is correct