oj.uz

Submission #953473

# Submission time Handle Problem Language Result Execution time Memory
953473 2024-03-26T03:01:27 Z pcc Port Facility (JOI17_port_facility) C++17
22 / 100
 2 ms 860 KB 
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second
#define ll long long

const ll mod = 1e9+7;
const int mxn = 4024;

ll pw(ll a,ll b){
	ll re = 1;
	while(b){
		if(b&1)re = re*a%mod;
		b>>=1;
		a = a*a%mod;
	}
	return re;
}
ll mad(ll a,ll b){
	a += b;
	return a>=mod?a-mod:a;
}


void print(priority_queue<pii,vector<pii>,less<pii>> pq){
	vector<pii> tmp;
	while(!pq.empty()){
		cerr<<pq.top().fs<<','<<pq.top().sc<<' ';
		tmp.push_back(pq.top());
		pq.pop();
	}
	cerr<<endl;
	return;
}

struct DSU{
	int dsu[mxn],sz[mxn];
	priority_queue<pii,vector<pii>,less<pii>> pq[mxn];
	DSU(){}
	void init(int n){
		for(int i = 0;i<=n;i++)dsu[i] = i,sz[i] = 1;
		return;
	}
	int root(int k){
		return k == dsu[k]?k:dsu[k] = root(dsu[k]);
	}
	void onion(int a,int b){
		a = root(a),b = root(b);
		if(a == b)return;
		if(sz[a]<sz[b])swap(a,b);
		dsu[b] = a;
		sz[a] += sz[b];
		if(pq[a].size()<pq[b].size())pq[a].swap(pq[b]);
		while(!pq[b].empty()){
			pq[a].push(pq[b].top());
			pq[b].pop();
		}
		return;
	}
};

pii arr[mxn];
int N;
int C = 0;
int col[mxn];
DSU dsu;
int op[mxn];
set<pii> st;
bitset<mxn> active;

void update(int r){
	r = dsu.root(r);
	if(!dsu.pq[r].empty()&&st.find(dsu.pq[r].top()) != st.end())st.erase(dsu.pq[r].top());
	while(!dsu.pq[r].empty()&&!active[dsu.pq[r].top().sc])dsu.pq[r].pop();
	if(!dsu.pq[r].empty())st.insert(dsu.pq[r].top());
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	dsu.init(N*2);
	for(int i = 1;i<=N;i++){
		cin>>arr[i].fs>>arr[i].sc;
		op[arr[i].fs] = i;
		op[arr[i].sc] = -i;
		dsu.pq[i*2].push(pii(arr[i].fs,i));
	}

	for(int i = 1;i<=N*2;i++){
		if(op[i]>0){
			active[op[i]] = true;
			update(op[i]*2);
			continue;
		}
		int pos = -op[i];
		active[pos] = false;
		update(dsu.root(pos*2));
		while(!st.empty()&&st.rbegin()->fs>arr[pos].fs){
			if(active[st.rbegin()->sc]){
				dsu.onion(pos*2-1,st.rbegin()->sc*2);
				dsu.onion(pos*2,st.rbegin()->sc*2-1);
			}
			st.erase(*st.rbegin());
		}
		update(dsu.root(pos*2-1));
		//cerr<<i<<":";for(auto &j:st)cerr<<j.fs<<','<<j.sc<<' ';cerr<<endl;
	}

	int ans = 0;
	for(int i = 1;i<=N;i++){
		if(dsu.root(i*2) == dsu.root(i*2-1)){
			cout<<0;
			return 0;
		}
		if(dsu.root(i*2) == i*2)ans++;
		if(dsu.root(i*2-1) == i*2-1)ans++;
	}
	cout<<pw(2,ans>>1);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 600 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 600 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 604 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 600 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 600 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 604 KB Output is correct
25 Correct 1 ms 600 KB Output is correct
26 Correct 2 ms 600 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 2 ms 604 KB Output is correct
32 Correct 1 ms 604 KB Output is correct
33 Correct 1 ms 856 KB Output is correct
34 Correct 1 ms 604 KB Output is correct
35 Correct 1 ms 604 KB Output is correct
36 Correct 1 ms 604 KB Output is correct
37 Correct 1 ms 604 KB Output is correct
38 Correct 2 ms 604 KB Output is correct
39 Correct 1 ms 604 KB Output is correct
40 Correct 1 ms 604 KB Output is correct
41 Correct 1 ms 600 KB Output is correct
42 Correct 1 ms 604 KB Output is correct
43 Correct 1 ms 604 KB Output is correct
44 Correct 1 ms 604 KB Output is correct

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 600 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 600 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 604 KB Output is correct
25 Correct 1 ms 600 KB Output is correct
26 Correct 2 ms 600 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 2 ms 604 KB Output is correct
32 Correct 1 ms 604 KB Output is correct
33 Correct 1 ms 856 KB Output is correct
34 Correct 1 ms 604 KB Output is correct
35 Correct 1 ms 604 KB Output is correct
36 Correct 1 ms 604 KB Output is correct
37 Correct 1 ms 604 KB Output is correct
38 Correct 2 ms 604 KB Output is correct
39 Correct 1 ms 604 KB Output is correct
40 Correct 1 ms 604 KB Output is correct
41 Correct 1 ms 600 KB Output is correct
42 Correct 1 ms 604 KB Output is correct
43 Correct 1 ms 604 KB Output is correct
44 Correct 1 ms 604 KB Output is correct
45 Runtime error 1 ms 860 KB Execution killed with signal 11
46 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 600 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 600 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 604 KB Output is correct
25 Correct 1 ms 600 KB Output is correct
26 Correct 2 ms 600 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 2 ms 604 KB Output is correct
32 Correct 1 ms 604 KB Output is correct
33 Correct 1 ms 856 KB Output is correct
34 Correct 1 ms 604 KB Output is correct
35 Correct 1 ms 604 KB Output is correct
36 Correct 1 ms 604 KB Output is correct
37 Correct 1 ms 604 KB Output is correct
38 Correct 2 ms 604 KB Output is correct
39 Correct 1 ms 604 KB Output is correct
40 Correct 1 ms 604 KB Output is correct
41 Correct 1 ms 600 KB Output is correct
42 Correct 1 ms 604 KB Output is correct
43 Correct 1 ms 604 KB Output is correct
44 Correct 1 ms 604 KB Output is correct
45 Runtime error 1 ms 860 KB Execution killed with signal 11
46 Halted 0 ms 0 KB -