oj.uz

Submission #975391

# Submission time Handle Problem Language Result Execution time Memory
975391 2024-05-05T05:17:23 Z LCJLY Port Facility (JOI17_port_facility) C++14
22 / 100
 6000 ms 421424 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,long long>pii;
typedef array<int,5>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

inline pii combine(pii a, pii b){
	if(a.first>b.first){
		return a;
	}
	else return b;
}

struct node{
	int s,e,m;
	node *l,*r;
	pii v;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1){
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
			v=combine(l->v,r->v);
		}
		else{
			v={0,s};
		}
	}
	
	void upd(int x, pii y){
		if(s==e){
			v=y;
			return;
		}
		if(x<=m) l->upd(x,y);
		else r->upd(x,y);
		v=combine(l->v,r->v);
	}
	
	pii query(int x, int y){
		if(x<=s&&y>=e){
			return v;
		}
		if(y<=m) return l->query(x,y);
		if(x>m) return r->query(x,y);
		return combine(l->query(x,m),r->query(m+1,y)); 
	}
};

vector<int>adj[1000005];
int visited[1000005];
bool amos=true;
const int mod=1e9+7;

void dfs(int index, int col){
	visited[index]=col;
	for(auto it:adj[index]){
		if(visited[it]&&visited[it]==visited[index]) amos=false;
		else if(!visited[it]){
			dfs(it,3-col);
		}
	}
}

struct DSU{
	vector<int>e;
	void init(int n){
		e=vector<int>(n,-1);
	}
	
	int get(int x){
		return e[x]<0?x:e[x]=get(e[x]);
	}
	
	bool sameSet(int x, int y){
		return get(x)==get(y);
	}
	
	bool unite(int x, int y){
		x=get(x);
		y=get(y);
		if(x==y) return 0;
		if(e[x]>e[y]) swap(x,y);
		e[x]+=e[y];
		e[y]=x;
		return 1;
	}
};

void solve(){
	int n;
	cin >> n;
	pii arr[n];
	for(int x=0;x<n;x++){
		cin >> arr[x].first >> arr[x].second;
	}
	
	sort(arr,arr+n);
	
	DSU dsu;
	dsu.init(2*n+5);
	node st(0,2*n+5);
	for(int x=0;x<n;x++){
		st.upd(arr[x].first,{arr[x].second,x});
	}
	
	for(int x=0;x<n;x++){
		vector<pii>undo;
		st.upd(arr[x].first,{0,x});
		while(1){
			pii hold=st.query(arr[x].first,arr[x].second);
			if(hold.first<=arr[x].second) break;
			adj[x].push_back(hold.second);
			adj[hold.second].push_back(x);
			dsu.unite(x,hold.second+n);
			dsu.unite(x+n,hold.second);
			if(dsu.sameSet(x,x+n)||dsu.sameSet(hold.second,hold.second+n)){
				cout << 0;
				return;
			}
			st.upd(arr[hold.second].first,{0,hold.second});
			undo.push_back(hold);
		}
		for(auto it:undo){
			st.upd(arr[it.second].first,{arr[it.second].second,it.second});
		}	
	}
	
	int counter=1;
	for(int x=0;x<n;x++){
		if(!visited[x]){
			dfs(x,1);
			counter=(counter*2)%mod;
		}
	}
	
	if(!amos){
		cout << 0;
	}
	else cout << counter;
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//freopen("in.txt","r",stdin);
	//cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25432 KB Output is correct
2 Correct 6 ms 25436 KB Output is correct
3 Correct 5 ms 25436 KB Output is correct
4 Correct 6 ms 25436 KB Output is correct
5 Correct 7 ms 25464 KB Output is correct
6 Correct 6 ms 25436 KB Output is correct
7 Correct 5 ms 25436 KB Output is correct
8 Correct 6 ms 25436 KB Output is correct
9 Correct 6 ms 25436 KB Output is correct
10 Correct 6 ms 25436 KB Output is correct
11 Correct 6 ms 25436 KB Output is correct
12 Correct 5 ms 25456 KB Output is correct
13 Correct 7 ms 25300 KB Output is correct
14 Correct 5 ms 25432 KB Output is correct
15 Correct 6 ms 25688 KB Output is correct
16 Correct 6 ms 25436 KB Output is correct
17 Correct 6 ms 25292 KB Output is correct
18 Correct 5 ms 25436 KB Output is correct
19 Correct 6 ms 25308 KB Output is correct
20 Correct 5 ms 25436 KB Output is correct
21 Correct 6 ms 25436 KB Output is correct
22 Correct 6 ms 25276 KB Output is correct
23 Correct 5 ms 25436 KB Output is correct
24 Correct 6 ms 25432 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25432 KB Output is correct
2 Correct 6 ms 25436 KB Output is correct
3 Correct 5 ms 25436 KB Output is correct
4 Correct 6 ms 25436 KB Output is correct
5 Correct 7 ms 25464 KB Output is correct
6 Correct 6 ms 25436 KB Output is correct
7 Correct 5 ms 25436 KB Output is correct
8 Correct 6 ms 25436 KB Output is correct
9 Correct 6 ms 25436 KB Output is correct
10 Correct 6 ms 25436 KB Output is correct
11 Correct 6 ms 25436 KB Output is correct
12 Correct 5 ms 25456 KB Output is correct
13 Correct 7 ms 25300 KB Output is correct
14 Correct 5 ms 25432 KB Output is correct
15 Correct 6 ms 25688 KB Output is correct
16 Correct 6 ms 25436 KB Output is correct
17 Correct 6 ms 25292 KB Output is correct
18 Correct 5 ms 25436 KB Output is correct
19 Correct 6 ms 25308 KB Output is correct
20 Correct 5 ms 25436 KB Output is correct
21 Correct 6 ms 25436 KB Output is correct
22 Correct 6 ms 25276 KB Output is correct
23 Correct 5 ms 25436 KB Output is correct
24 Correct 6 ms 25432 KB Output is correct
25 Correct 11 ms 26460 KB Output is correct
26 Correct 14 ms 26772 KB Output is correct
27 Correct 12 ms 26460 KB Output is correct
28 Correct 15 ms 26952 KB Output is correct
29 Correct 13 ms 26460 KB Output is correct
30 Correct 15 ms 26716 KB Output is correct
31 Correct 13 ms 26712 KB Output is correct
32 Correct 11 ms 26460 KB Output is correct
33 Correct 10 ms 26200 KB Output is correct
34 Correct 7 ms 26144 KB Output is correct
35 Correct 7 ms 25948 KB Output is correct
36 Correct 7 ms 25948 KB Output is correct
37 Correct 7 ms 25944 KB Output is correct
38 Correct 6 ms 25948 KB Output is correct
39 Correct 7 ms 25948 KB Output is correct
40 Correct 7 ms 25944 KB Output is correct
41 Correct 183 ms 42200 KB Output is correct
42 Correct 188 ms 42140 KB Output is correct
43 Correct 7 ms 25948 KB Output is correct
44 Correct 8 ms 26048 KB Output is correct

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25432 KB Output is correct
2 Correct 6 ms 25436 KB Output is correct
3 Correct 5 ms 25436 KB Output is correct
4 Correct 6 ms 25436 KB Output is correct
5 Correct 7 ms 25464 KB Output is correct
6 Correct 6 ms 25436 KB Output is correct
7 Correct 5 ms 25436 KB Output is correct
8 Correct 6 ms 25436 KB Output is correct
9 Correct 6 ms 25436 KB Output is correct
10 Correct 6 ms 25436 KB Output is correct
11 Correct 6 ms 25436 KB Output is correct
12 Correct 5 ms 25456 KB Output is correct
13 Correct 7 ms 25300 KB Output is correct
14 Correct 5 ms 25432 KB Output is correct
15 Correct 6 ms 25688 KB Output is correct
16 Correct 6 ms 25436 KB Output is correct
17 Correct 6 ms 25292 KB Output is correct
18 Correct 5 ms 25436 KB Output is correct
19 Correct 6 ms 25308 KB Output is correct
20 Correct 5 ms 25436 KB Output is correct
21 Correct 6 ms 25436 KB Output is correct
22 Correct 6 ms 25276 KB Output is correct
23 Correct 5 ms 25436 KB Output is correct
24 Correct 6 ms 25432 KB Output is correct
25 Correct 11 ms 26460 KB Output is correct
26 Correct 14 ms 26772 KB Output is correct
27 Correct 12 ms 26460 KB Output is correct
28 Correct 15 ms 26952 KB Output is correct
29 Correct 13 ms 26460 KB Output is correct
30 Correct 15 ms 26716 KB Output is correct
31 Correct 13 ms 26712 KB Output is correct
32 Correct 11 ms 26460 KB Output is correct
33 Correct 10 ms 26200 KB Output is correct
34 Correct 7 ms 26144 KB Output is correct
35 Correct 7 ms 25948 KB Output is correct
36 Correct 7 ms 25948 KB Output is correct
37 Correct 7 ms 25944 KB Output is correct
38 Correct 6 ms 25948 KB Output is correct
39 Correct 7 ms 25948 KB Output is correct
40 Correct 7 ms 25944 KB Output is correct
41 Correct 183 ms 42200 KB Output is correct
42 Correct 188 ms 42140 KB Output is correct
43 Correct 7 ms 25948 KB Output is correct
44 Correct 8 ms 26048 KB Output is correct
45 Correct 701 ms 107668 KB Output is correct
46 Correct 1707 ms 190428 KB Output is correct
47 Correct 413 ms 81236 KB Output is correct
48 Correct 1702 ms 186020 KB Output is correct
49 Correct 548 ms 94968 KB Output is correct
50 Correct 887 ms 124972 KB Output is correct
51 Correct 549 ms 96168 KB Output is correct
52 Correct 69 ms 54396 KB Output is correct
53 Correct 78 ms 54348 KB Output is correct
54 Correct 86 ms 58936 KB Output is correct
55 Correct 65 ms 56124 KB Output is correct
56 Correct 65 ms 56128 KB Output is correct
57 Correct 88 ms 57344 KB Output is correct
58 Correct 70 ms 54352 KB Output is correct
59 Correct 81 ms 54896 KB Output is correct
60 Correct 103 ms 56400 KB Output is correct
61 Correct 141 ms 58800 KB Output is correct
62 Correct 64 ms 55108 KB Output is correct
63 Correct 57 ms 54268 KB Output is correct
64 Correct 60 ms 54284 KB Output is correct
65 Correct 94 ms 56184 KB Output is correct
66 Correct 91 ms 56372 KB Output is correct
67 Execution timed out 6081 ms 421424 KB Time limit exceeded
68 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25432 KB Output is correct
2 Correct 6 ms 25436 KB Output is correct
3 Correct 5 ms 25436 KB Output is correct
4 Correct 6 ms 25436 KB Output is correct
5 Correct 7 ms 25464 KB Output is correct
6 Correct 6 ms 25436 KB Output is correct
7 Correct 5 ms 25436 KB Output is correct
8 Correct 6 ms 25436 KB Output is correct
9 Correct 6 ms 25436 KB Output is correct
10 Correct 6 ms 25436 KB Output is correct
11 Correct 6 ms 25436 KB Output is correct
12 Correct 5 ms 25456 KB Output is correct
13 Correct 7 ms 25300 KB Output is correct
14 Correct 5 ms 25432 KB Output is correct
15 Correct 6 ms 25688 KB Output is correct
16 Correct 6 ms 25436 KB Output is correct
17 Correct 6 ms 25292 KB Output is correct
18 Correct 5 ms 25436 KB Output is correct
19 Correct 6 ms 25308 KB Output is correct
20 Correct 5 ms 25436 KB Output is correct
21 Correct 6 ms 25436 KB Output is correct
22 Correct 6 ms 25276 KB Output is correct
23 Correct 5 ms 25436 KB Output is correct
24 Correct 6 ms 25432 KB Output is correct
25 Correct 11 ms 26460 KB Output is correct
26 Correct 14 ms 26772 KB Output is correct
27 Correct 12 ms 26460 KB Output is correct
28 Correct 15 ms 26952 KB Output is correct
29 Correct 13 ms 26460 KB Output is correct
30 Correct 15 ms 26716 KB Output is correct
31 Correct 13 ms 26712 KB Output is correct
32 Correct 11 ms 26460 KB Output is correct
33 Correct 10 ms 26200 KB Output is correct
34 Correct 7 ms 26144 KB Output is correct
35 Correct 7 ms 25948 KB Output is correct
36 Correct 7 ms 25948 KB Output is correct
37 Correct 7 ms 25944 KB Output is correct
38 Correct 6 ms 25948 KB Output is correct
39 Correct 7 ms 25948 KB Output is correct
40 Correct 7 ms 25944 KB Output is correct
41 Correct 183 ms 42200 KB Output is correct
42 Correct 188 ms 42140 KB Output is correct
43 Correct 7 ms 25948 KB Output is correct
44 Correct 8 ms 26048 KB Output is correct
45 Correct 701 ms 107668 KB Output is correct
46 Correct 1707 ms 190428 KB Output is correct
47 Correct 413 ms 81236 KB Output is correct
48 Correct 1702 ms 186020 KB Output is correct
49 Correct 548 ms 94968 KB Output is correct
50 Correct 887 ms 124972 KB Output is correct
51 Correct 549 ms 96168 KB Output is correct
52 Correct 69 ms 54396 KB Output is correct
53 Correct 78 ms 54348 KB Output is correct
54 Correct 86 ms 58936 KB Output is correct
55 Correct 65 ms 56124 KB Output is correct
56 Correct 65 ms 56128 KB Output is correct
57 Correct 88 ms 57344 KB Output is correct
58 Correct 70 ms 54352 KB Output is correct
59 Correct 81 ms 54896 KB Output is correct
60 Correct 103 ms 56400 KB Output is correct
61 Correct 141 ms 58800 KB Output is correct
62 Correct 64 ms 55108 KB Output is correct
63 Correct 57 ms 54268 KB Output is correct
64 Correct 60 ms 54284 KB Output is correct
65 Correct 94 ms 56184 KB Output is correct
66 Correct 91 ms 56372 KB Output is correct
67 Execution timed out 6081 ms 421424 KB Time limit exceeded
68 Halted 0 ms 0 KB -