oj.uz

Submission #892799

# Submission time Handle Problem Language Result Execution time Memory
892799 2023-12-26T02:09:34 Z ReLice Port Facility (JOI17_port_facility) C++17
100 / 100
 3557 ms 304148 KB 
#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define bc back()
#define ar array
#define vll vector<ll> 
using namespace std;/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;*/
template <class _T>
bool chmin(_T &x, const _T &y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template <class _T>
bool chmax(_T &x, const _T &y){
    bool flag=false;
    if (x<y){
        x=y;flag|=true;
    }
    return flag;
}
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=2e18+7;
const ll mod=1e9+7;
const ll N=2e6+7;
struct st{
	ll t[N*4];
	st(){
		for(ll i=0;i<N*4;i++)t[i]=-inf;
	}
	void upd(ll pos,ll val,ll v=1,ll tl=1,ll tr=N){
		if(tl>pos || tr<pos)return;
		if(tl==tr){
			t[v]=val;
			return;
		}
		ll tm=(tl+tr)/2;
		upd(pos,val,v*2,tl,tm);
		upd(pos,val,v*2+1,tm+1,tr);
		t[v]=max(t[v*2],t[v*2+1]);
	}
	ll get(ll l,ll r,ll v=1,ll tl=1,ll tr=N){
		if(tl>r || tr<l)return -inf;
		if(l<=tl && tr<=r)return t[v];
		ll tm=(tl+tr)/2;
		return max(get(l,r,v*2,tl,tm),get(l,r,v*2+1,tm+1,tr));
	}
}mx,mn;
ll vis[N];
ll id[N];
ll a[N],b[N];
ll type[N];
vll vt[2];
void dfs(ll v){
	vis[v]++;
	mx.upd(a[v],-inf);
	mn.upd(b[v],-inf);
	vt[type[v]].pb(v);
	while(true){
		ll i=mx.get(a[v],b[v]);
		if(b[v]<i){
			type[id[i]]=type[v]^1;
			dfs(id[i]);
			continue;
		}
		ll j=-mn.get(a[v],b[v]);
		if(a[v]>j){
			type[id[j]]=type[v]^1;
			dfs(id[j]);
			continue;
		}
		break;
	}
}
bool check(vll v){
	for(auto i : v){
		mn.upd(b[i],-a[i]);
		mx.upd(a[i],b[i]);
	}
	for(auto i : v){
		ll x=mx.get(a[i],b[i]);
		if(x>b[i])return true;
		x=-mn.get(a[i],b[i]);
		if(a[i]>x)return true;
	}
	for(auto i : v){
		mn.upd(b[i],-inf);
		mx.upd(a[i],-inf);
	}
	return false;
}
void solve(){
	ll i;
	ll n;
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		mx.upd(a[i],b[i]);
		mn.upd(b[i],-a[i]);
		id[a[i]]=i;
		id[b[i]]=i;
	}
	ll ans=1;
	for(i=1;i<=n;i++){
		if(vis[i])continue;
		vt[0].clear();
		vt[1].clear();
		dfs(i);
		if(check(vt[1]) || check(vt[0])){
			cout<<0<<endl;
			return;
		}
		ans*=2;
		ans%=mod;
	}
	cout<<ans<<endl;
}
signed main(){
	//start();
    ll t=1;
	//cin>>t;
    while(t--) solve();
    return 0;
}
/*
35
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
25 26
27 28
29 30
31 32
33 34
35 36
37 38
39 40
41 42
43 44
45 46
47 48
49 50
51 52
53 54
55 56
57 58
59 60
61 62
63 64
65 66
67 68
69 70






*/

Compilation message

port_facility.cpp: In function 'void fre(std::string)':
port_facility.cpp:42:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:42:64: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 131844 KB Output is correct
2 Correct 20 ms 131932 KB Output is correct
3 Correct 19 ms 131920 KB Output is correct
4 Correct 18 ms 131928 KB Output is correct
5 Correct 19 ms 131928 KB Output is correct
6 Correct 19 ms 132176 KB Output is correct
7 Correct 19 ms 131924 KB Output is correct
8 Correct 18 ms 131896 KB Output is correct
9 Correct 19 ms 131932 KB Output is correct
10 Correct 19 ms 131932 KB Output is correct
11 Correct 19 ms 131864 KB Output is correct
12 Correct 18 ms 131932 KB Output is correct
13 Correct 18 ms 131924 KB Output is correct
14 Correct 19 ms 131896 KB Output is correct
15 Correct 18 ms 131972 KB Output is correct
16 Correct 19 ms 131980 KB Output is correct
17 Correct 18 ms 131856 KB Output is correct
18 Correct 18 ms 131924 KB Output is correct
19 Correct 19 ms 131840 KB Output is correct
20 Correct 19 ms 131932 KB Output is correct
21 Correct 20 ms 131844 KB Output is correct
22 Correct 19 ms 131932 KB Output is correct
23 Correct 19 ms 131932 KB Output is correct
24 Correct 19 ms 131784 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 131844 KB Output is correct
2 Correct 20 ms 131932 KB Output is correct
3 Correct 19 ms 131920 KB Output is correct
4 Correct 18 ms 131928 KB Output is correct
5 Correct 19 ms 131928 KB Output is correct
6 Correct 19 ms 132176 KB Output is correct
7 Correct 19 ms 131924 KB Output is correct
8 Correct 18 ms 131896 KB Output is correct
9 Correct 19 ms 131932 KB Output is correct
10 Correct 19 ms 131932 KB Output is correct
11 Correct 19 ms 131864 KB Output is correct
12 Correct 18 ms 131932 KB Output is correct
13 Correct 18 ms 131924 KB Output is correct
14 Correct 19 ms 131896 KB Output is correct
15 Correct 18 ms 131972 KB Output is correct
16 Correct 19 ms 131980 KB Output is correct
17 Correct 18 ms 131856 KB Output is correct
18 Correct 18 ms 131924 KB Output is correct
19 Correct 19 ms 131840 KB Output is correct
20 Correct 19 ms 131932 KB Output is correct
21 Correct 20 ms 131844 KB Output is correct
22 Correct 19 ms 131932 KB Output is correct
23 Correct 19 ms 131932 KB Output is correct
24 Correct 19 ms 131784 KB Output is correct
25 Correct 24 ms 131972 KB Output is correct
26 Correct 23 ms 131932 KB Output is correct
27 Correct 22 ms 131972 KB Output is correct
28 Correct 23 ms 131932 KB Output is correct
29 Correct 22 ms 131924 KB Output is correct
30 Correct 22 ms 131928 KB Output is correct
31 Correct 22 ms 132132 KB Output is correct
32 Correct 22 ms 131932 KB Output is correct
33 Correct 21 ms 131896 KB Output is correct
34 Correct 21 ms 131932 KB Output is correct
35 Correct 22 ms 131856 KB Output is correct
36 Correct 23 ms 131916 KB Output is correct
37 Correct 21 ms 132228 KB Output is correct
38 Correct 21 ms 131932 KB Output is correct
39 Correct 22 ms 131888 KB Output is correct
40 Correct 22 ms 131940 KB Output is correct
41 Correct 22 ms 132228 KB Output is correct
42 Correct 23 ms 132180 KB Output is correct
43 Correct 21 ms 132180 KB Output is correct
44 Correct 23 ms 132188 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 131844 KB Output is correct
2 Correct 20 ms 131932 KB Output is correct
3 Correct 19 ms 131920 KB Output is correct
4 Correct 18 ms 131928 KB Output is correct
5 Correct 19 ms 131928 KB Output is correct
6 Correct 19 ms 132176 KB Output is correct
7 Correct 19 ms 131924 KB Output is correct
8 Correct 18 ms 131896 KB Output is correct
9 Correct 19 ms 131932 KB Output is correct
10 Correct 19 ms 131932 KB Output is correct
11 Correct 19 ms 131864 KB Output is correct
12 Correct 18 ms 131932 KB Output is correct
13 Correct 18 ms 131924 KB Output is correct
14 Correct 19 ms 131896 KB Output is correct
15 Correct 18 ms 131972 KB Output is correct
16 Correct 19 ms 131980 KB Output is correct
17 Correct 18 ms 131856 KB Output is correct
18 Correct 18 ms 131924 KB Output is correct
19 Correct 19 ms 131840 KB Output is correct
20 Correct 19 ms 131932 KB Output is correct
21 Correct 20 ms 131844 KB Output is correct
22 Correct 19 ms 131932 KB Output is correct
23 Correct 19 ms 131932 KB Output is correct
24 Correct 19 ms 131784 KB Output is correct
25 Correct 24 ms 131972 KB Output is correct
26 Correct 23 ms 131932 KB Output is correct
27 Correct 22 ms 131972 KB Output is correct
28 Correct 23 ms 131932 KB Output is correct
29 Correct 22 ms 131924 KB Output is correct
30 Correct 22 ms 131928 KB Output is correct
31 Correct 22 ms 132132 KB Output is correct
32 Correct 22 ms 131932 KB Output is correct
33 Correct 21 ms 131896 KB Output is correct
34 Correct 21 ms 131932 KB Output is correct
35 Correct 22 ms 131856 KB Output is correct
36 Correct 23 ms 131916 KB Output is correct
37 Correct 21 ms 132228 KB Output is correct
38 Correct 21 ms 131932 KB Output is correct
39 Correct 22 ms 131888 KB Output is correct
40 Correct 22 ms 131940 KB Output is correct
41 Correct 22 ms 132228 KB Output is correct
42 Correct 23 ms 132180 KB Output is correct
43 Correct 21 ms 132180 KB Output is correct
44 Correct 23 ms 132188 KB Output is correct
45 Correct 248 ms 139856 KB Output is correct
46 Correct 256 ms 141488 KB Output is correct
47 Correct 243 ms 138836 KB Output is correct
48 Correct 257 ms 141256 KB Output is correct
49 Correct 242 ms 139116 KB Output is correct
50 Correct 140 ms 140832 KB Output is correct
51 Correct 128 ms 140636 KB Output is correct
52 Correct 236 ms 136276 KB Output is correct
53 Correct 271 ms 135928 KB Output is correct
54 Correct 188 ms 148964 KB Output is correct
55 Correct 141 ms 143820 KB Output is correct
56 Correct 139 ms 143564 KB Output is correct
57 Correct 239 ms 138068 KB Output is correct
58 Correct 238 ms 136040 KB Output is correct
59 Correct 264 ms 138264 KB Output is correct
60 Correct 253 ms 138068 KB Output is correct
61 Correct 252 ms 138232 KB Output is correct
62 Correct 118 ms 138856 KB Output is correct
63 Correct 110 ms 138580 KB Output is correct
64 Correct 106 ms 138580 KB Output is correct
65 Correct 223 ms 148972 KB Output is correct
66 Correct 219 ms 148936 KB Output is correct
67 Correct 250 ms 144556 KB Output is correct
68 Correct 244 ms 144756 KB Output is correct
69 Correct 242 ms 143852 KB Output is correct
70 Correct 258 ms 144056 KB Output is correct
71 Correct 246 ms 149224 KB Output is correct
72 Correct 251 ms 149440 KB Output is correct
73 Correct 237 ms 146116 KB Output is correct
74 Correct 239 ms 146112 KB Output is correct
75 Correct 214 ms 145756 KB Output is correct
76 Correct 209 ms 149448 KB Output is correct
77 Correct 187 ms 149440 KB Output is correct
78 Correct 254 ms 141320 KB Output is correct
79 Correct 243 ms 140052 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 131844 KB Output is correct
2 Correct 20 ms 131932 KB Output is correct
3 Correct 19 ms 131920 KB Output is correct
4 Correct 18 ms 131928 KB Output is correct
5 Correct 19 ms 131928 KB Output is correct
6 Correct 19 ms 132176 KB Output is correct
7 Correct 19 ms 131924 KB Output is correct
8 Correct 18 ms 131896 KB Output is correct
9 Correct 19 ms 131932 KB Output is correct
10 Correct 19 ms 131932 KB Output is correct
11 Correct 19 ms 131864 KB Output is correct
12 Correct 18 ms 131932 KB Output is correct
13 Correct 18 ms 131924 KB Output is correct
14 Correct 19 ms 131896 KB Output is correct
15 Correct 18 ms 131972 KB Output is correct
16 Correct 19 ms 131980 KB Output is correct
17 Correct 18 ms 131856 KB Output is correct
18 Correct 18 ms 131924 KB Output is correct
19 Correct 19 ms 131840 KB Output is correct
20 Correct 19 ms 131932 KB Output is correct
21 Correct 20 ms 131844 KB Output is correct
22 Correct 19 ms 131932 KB Output is correct
23 Correct 19 ms 131932 KB Output is correct
24 Correct 19 ms 131784 KB Output is correct
25 Correct 24 ms 131972 KB Output is correct
26 Correct 23 ms 131932 KB Output is correct
27 Correct 22 ms 131972 KB Output is correct
28 Correct 23 ms 131932 KB Output is correct
29 Correct 22 ms 131924 KB Output is correct
30 Correct 22 ms 131928 KB Output is correct
31 Correct 22 ms 132132 KB Output is correct
32 Correct 22 ms 131932 KB Output is correct
33 Correct 21 ms 131896 KB Output is correct
34 Correct 21 ms 131932 KB Output is correct
35 Correct 22 ms 131856 KB Output is correct
36 Correct 23 ms 131916 KB Output is correct
37 Correct 21 ms 132228 KB Output is correct
38 Correct 21 ms 131932 KB Output is correct
39 Correct 22 ms 131888 KB Output is correct
40 Correct 22 ms 131940 KB Output is correct
41 Correct 22 ms 132228 KB Output is correct
42 Correct 23 ms 132180 KB Output is correct
43 Correct 21 ms 132180 KB Output is correct
44 Correct 23 ms 132188 KB Output is correct
45 Correct 248 ms 139856 KB Output is correct
46 Correct 256 ms 141488 KB Output is correct
47 Correct 243 ms 138836 KB Output is correct
48 Correct 257 ms 141256 KB Output is correct
49 Correct 242 ms 139116 KB Output is correct
50 Correct 140 ms 140832 KB Output is correct
51 Correct 128 ms 140636 KB Output is correct
52 Correct 236 ms 136276 KB Output is correct
53 Correct 271 ms 135928 KB Output is correct
54 Correct 188 ms 148964 KB Output is correct
55 Correct 141 ms 143820 KB Output is correct
56 Correct 139 ms 143564 KB Output is correct
57 Correct 239 ms 138068 KB Output is correct
58 Correct 238 ms 136040 KB Output is correct
59 Correct 264 ms 138264 KB Output is correct
60 Correct 253 ms 138068 KB Output is correct
61 Correct 252 ms 138232 KB Output is correct
62 Correct 118 ms 138856 KB Output is correct
63 Correct 110 ms 138580 KB Output is correct
64 Correct 106 ms 138580 KB Output is correct
65 Correct 223 ms 148972 KB Output is correct
66 Correct 219 ms 148936 KB Output is correct
67 Correct 250 ms 144556 KB Output is correct
68 Correct 244 ms 144756 KB Output is correct
69 Correct 242 ms 143852 KB Output is correct
70 Correct 258 ms 144056 KB Output is correct
71 Correct 246 ms 149224 KB Output is correct
72 Correct 251 ms 149440 KB Output is correct
73 Correct 237 ms 146116 KB Output is correct
74 Correct 239 ms 146112 KB Output is correct
75 Correct 214 ms 145756 KB Output is correct
76 Correct 209 ms 149448 KB Output is correct
77 Correct 187 ms 149440 KB Output is correct
78 Correct 254 ms 141320 KB Output is correct
79 Correct 243 ms 140052 KB Output is correct
80 Correct 3107 ms 201492 KB Output is correct
81 Correct 3037 ms 199616 KB Output is correct
82 Correct 2937 ms 196160 KB Output is correct
83 Correct 3059 ms 200028 KB Output is correct
84 Correct 3043 ms 201480 KB Output is correct
85 Correct 1301 ms 197356 KB Output is correct
86 Correct 1457 ms 201744 KB Output is correct
87 Correct 2955 ms 184120 KB Output is correct
88 Correct 3520 ms 183636 KB Output is correct
89 Correct 2445 ms 300204 KB Output is correct
90 Correct 1737 ms 246756 KB Output is correct
91 Correct 1772 ms 246832 KB Output is correct
92 Correct 2939 ms 193872 KB Output is correct
93 Correct 2895 ms 184120 KB Output is correct
94 Correct 3242 ms 194064 KB Output is correct
95 Correct 3052 ms 193924 KB Output is correct
96 Correct 2924 ms 194148 KB Output is correct
97 Correct 1376 ms 196804 KB Output is correct
98 Correct 1350 ms 195888 KB Output is correct
99 Correct 1706 ms 201364 KB Output is correct
100 Correct 3539 ms 300008 KB Output is correct
101 Correct 3557 ms 299744 KB Output is correct
102 Correct 3243 ms 256664 KB Output is correct
103 Correct 3294 ms 257028 KB Output is correct
104 Correct 3167 ms 252752 KB Output is correct
105 Correct 3259 ms 251952 KB Output is correct
106 Correct 3274 ms 303848 KB Output is correct
107 Correct 3264 ms 303772 KB Output is correct
108 Correct 3184 ms 272056 KB Output is correct
109 Correct 3133 ms 274032 KB Output is correct
110 Correct 2978 ms 302140 KB Output is correct
111 Correct 2889 ms 304148 KB Output is correct
112 Correct 2633 ms 303888 KB Output is correct
113 Correct 2986 ms 195324 KB Output is correct
114 Correct 3037 ms 199392 KB Output is correct