oj.uz

답안 #975739

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
975739 2024-05-05T19:49:19 Z starchan Port Facility (JOI17_port_facility) C++17
78 / 100
 1817 ms 1048576 KB 
#include<bits/stdc++.h>
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
 
const int SMX = 1e6+5;
const int MX = 2e6+3;
const int LMX = 3e7;
const int mod = 1e9+7;
 
vector<vector<int>> g;
 
int leaf[MX]; 
vector<int> lleft;
vector<int> rright;
vector<bool> tree;
int nxt = 0;

int New()
{
	lleft.pb(-1); rright.pb(-1); g.resize(g.size()+1); tree.pb(0);
	return nxt++;
}
 
int build(int l, int r)
{
	int id = New(); int m = (l+r)/2;
	if(l==r)
		return id;
	lleft[id] = build(l, m); rright[id] = build(m+1, r);  tree[id] = 0;
	return id;
}
 
int upd(int pos, int id, int l, int r)
{
	int id_n = New(); tree[id_n] = 1;
	if(l == r)
		return leaf[pos] = id_n;
	lleft[id_n] = lleft[id]; rright[id_n] = rright[id];
	int m = (l+r)/2;
	if(pos <= m)
		lleft[id_n] = upd(pos, lleft[id], l, m);
	else
		rright[id_n] = upd(pos, rright[id], m+1, r);
	return id_n;
}
 
void add(int pp, int ql, int qr, int id, int l, int r)
{
	if(qr < l || r < ql)
		return;
	if((ql <= l) && (r <= qr))
	{
		g[pp].pb(id);
		return;
	}
	int m = (l+r)/2;
	add(pp, ql, qr, lleft[id], l, m);
	add(pp, ql, qr, rright[id], m+1, r);
	return;
}
 
vector<int> pa; vector<bool> col; bool works = true;
 
int leader(int u)
{
	if(pa[u] < 0)
		return u;
	else
	{
		int p = leader(pa[u]);
		col[u] = col[u]^col[pa[u]];
		return pa[u] = p;
	}
}
 
void merge(int u, int v, int xr)
{
	int x = leader(u);
	int y = leader(v);
	if(x == y)
	{
		if(col[u]^col[v]^xr)
			works = false;
		return;
	}
	if(pa[x] < pa[y])
	{
		swap(x, y);
		swap(u, v);
	}
	pa[y]+=pa[x];
	pa[x] = y;
	col[x] = col[u]^col[v]^xr;
	return;
}
bitset<LMX> vis, ppl;
void dfs(int u)
{
	vis[u] = 1;
	if(lleft[u] != -1)
	{
		if((!vis[lleft[u]]) && tree[lleft[u]])
			dfs(lleft[u]);
		if((!vis[rright[u]]) && tree[rright[u]])
			dfs(rright[u]);
		if(tree[lleft[u]]){
		//cout << "cat_L_Calling " << lleft[u] << " from " << u << endl;
		merge(u, lleft[u], 0);}
		if(tree[rright[u]]){
		//cout << "cat_R_Calling " << rright[u] << " from " << u << endl;
		merge(u, rright[u], 0);}
		return;
	}
	for(int v: g[u])
	{
		if(!tree[v])
			continue;
		merge(u, v, 1);
		if(vis[v])
		{
			//cout << "Tried to call " << v << " from " << u << endl;
			continue;
		}
		//cout << "Calling " << v << " from " << u <<  "\n";
		dfs(v);
	}
	return;
}
 
signed main()
{
	fast();//During debugging, this should ideally be removed.
	int n;
	cin >> n;
	vector<in> vv(n+1);
	for(int i = 1; i <= n; i++)
		cin >> vv[i][0] >> vv[i][1];
	sort(vv.begin()+1, vv.end());
	int sn = 0; int root = build(1, 2*n); //cout << "nxt = " << nxt << endl;
 
	int b[n+1];
	for(int i = 1; i <= n; i++)
	{
		root = upd(vv[i][1], root, 1, 2*n);
		add(leaf[vv[i][1]], vv[i][0], vv[i][1]-1, root, 1, 2*n);
		b[++sn] = leaf[vv[i][1]];
		//cout << "b[sn] = " << b[sn] << endl;
	}

	int N = g.size(); pa.assign(N, -1); col.assign(N, 0);
	for(int i = 1; i <= n; i++)
		dfs(b[i]);
	if(!works)
	{
		cout << "0\n";
		return 0;
	}
	int ans = 1;
	for(int i = 1; i <= n; i++)
	{
		if(ppl[leader(b[i])])
			continue;
		ppl[leader(b[i])] = 1; ans*=2; ans%=mod;
	}
	cout << ans << "\n";
	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4596 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 2 ms 4696 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Correct 1 ms 4444 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4596 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 2 ms 4696 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Correct 1 ms 4444 KB Output is correct
25 Correct 4 ms 5892 KB Output is correct
26 Correct 4 ms 5892 KB Output is correct
27 Correct 4 ms 6144 KB Output is correct
28 Correct 4 ms 5892 KB Output is correct
29 Correct 4 ms 5896 KB Output is correct
30 Correct 3 ms 5892 KB Output is correct
31 Correct 4 ms 5892 KB Output is correct
32 Correct 4 ms 5888 KB Output is correct
33 Correct 4 ms 5888 KB Output is correct
34 Correct 3 ms 5916 KB Output is correct
35 Correct 3 ms 5892 KB Output is correct
36 Correct 3 ms 5892 KB Output is correct
37 Correct 4 ms 5948 KB Output is correct
38 Correct 4 ms 5892 KB Output is correct
39 Correct 4 ms 6092 KB Output is correct
40 Correct 3 ms 5892 KB Output is correct
41 Correct 3 ms 5892 KB Output is correct
42 Correct 5 ms 5892 KB Output is correct
43 Correct 3 ms 5892 KB Output is correct
44 Correct 3 ms 5892 KB Output is correct

Subtask #3
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4596 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 2 ms 4696 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Correct 1 ms 4444 KB Output is correct
25 Correct 4 ms 5892 KB Output is correct
26 Correct 4 ms 5892 KB Output is correct
27 Correct 4 ms 6144 KB Output is correct
28 Correct 4 ms 5892 KB Output is correct
29 Correct 4 ms 5896 KB Output is correct
30 Correct 3 ms 5892 KB Output is correct
31 Correct 4 ms 5892 KB Output is correct
32 Correct 4 ms 5888 KB Output is correct
33 Correct 4 ms 5888 KB Output is correct
34 Correct 3 ms 5916 KB Output is correct
35 Correct 3 ms 5892 KB Output is correct
36 Correct 3 ms 5892 KB Output is correct
37 Correct 4 ms 5948 KB Output is correct
38 Correct 4 ms 5892 KB Output is correct
39 Correct 4 ms 6092 KB Output is correct
40 Correct 3 ms 5892 KB Output is correct
41 Correct 3 ms 5892 KB Output is correct
42 Correct 5 ms 5892 KB Output is correct
43 Correct 3 ms 5892 KB Output is correct
44 Correct 3 ms 5892 KB Output is correct
45 Correct 197 ms 151772 KB Output is correct
46 Correct 151 ms 149972 KB Output is correct
47 Correct 148 ms 152692 KB Output is correct
48 Correct 158 ms 152148 KB Output is correct
49 Correct 146 ms 154612 KB Output is correct
50 Correct 158 ms 151508 KB Output is correct
51 Correct 148 ms 149972 KB Output is correct
52 Correct 113 ms 142800 KB Output is correct
53 Correct 145 ms 153028 KB Output is correct
54 Correct 162 ms 151508 KB Output is correct
55 Correct 156 ms 152236 KB Output is correct
56 Correct 159 ms 150740 KB Output is correct
57 Correct 133 ms 142580 KB Output is correct
58 Correct 118 ms 141920 KB Output is correct
59 Correct 130 ms 152728 KB Output is correct
60 Correct 141 ms 153460 KB Output is correct
61 Correct 144 ms 151808 KB Output is correct
62 Correct 135 ms 150992 KB Output is correct
63 Correct 139 ms 149812 KB Output is correct
64 Correct 141 ms 152236 KB Output is correct
65 Correct 245 ms 153864 KB Output is correct
66 Correct 249 ms 150672 KB Output is correct
67 Correct 160 ms 153048 KB Output is correct
68 Correct 164 ms 151020 KB Output is correct
69 Correct 166 ms 153048 KB Output is correct
70 Correct 157 ms 150444 KB Output is correct
71 Correct 153 ms 149352 KB Output is correct
72 Correct 152 ms 153784 KB Output is correct
73 Correct 148 ms 153304 KB Output is correct
74 Correct 149 ms 151908 KB Output is correct
75 Correct 125 ms 142040 KB Output is correct
76 Correct 128 ms 142352 KB Output is correct
77 Correct 129 ms 143600 KB Output is correct
78 Correct 155 ms 151720 KB Output is correct
79 Correct 150 ms 152096 KB Output is correct

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4596 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 2 ms 4696 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Correct 1 ms 4444 KB Output is correct
25 Correct 4 ms 5892 KB Output is correct
26 Correct 4 ms 5892 KB Output is correct
27 Correct 4 ms 6144 KB Output is correct
28 Correct 4 ms 5892 KB Output is correct
29 Correct 4 ms 5896 KB Output is correct
30 Correct 3 ms 5892 KB Output is correct
31 Correct 4 ms 5892 KB Output is correct
32 Correct 4 ms 5888 KB Output is correct
33 Correct 4 ms 5888 KB Output is correct
34 Correct 3 ms 5916 KB Output is correct
35 Correct 3 ms 5892 KB Output is correct
36 Correct 3 ms 5892 KB Output is correct
37 Correct 4 ms 5948 KB Output is correct
38 Correct 4 ms 5892 KB Output is correct
39 Correct 4 ms 6092 KB Output is correct
40 Correct 3 ms 5892 KB Output is correct
41 Correct 3 ms 5892 KB Output is correct
42 Correct 5 ms 5892 KB Output is correct
43 Correct 3 ms 5892 KB Output is correct
44 Correct 3 ms 5892 KB Output is correct
45 Correct 197 ms 151772 KB Output is correct
46 Correct 151 ms 149972 KB Output is correct
47 Correct 148 ms 152692 KB Output is correct
48 Correct 158 ms 152148 KB Output is correct
49 Correct 146 ms 154612 KB Output is correct
50 Correct 158 ms 151508 KB Output is correct
51 Correct 148 ms 149972 KB Output is correct
52 Correct 113 ms 142800 KB Output is correct
53 Correct 145 ms 153028 KB Output is correct
54 Correct 162 ms 151508 KB Output is correct
55 Correct 156 ms 152236 KB Output is correct
56 Correct 159 ms 150740 KB Output is correct
57 Correct 133 ms 142580 KB Output is correct
58 Correct 118 ms 141920 KB Output is correct
59 Correct 130 ms 152728 KB Output is correct
60 Correct 141 ms 153460 KB Output is correct
61 Correct 144 ms 151808 KB Output is correct
62 Correct 135 ms 150992 KB Output is correct
63 Correct 139 ms 149812 KB Output is correct
64 Correct 141 ms 152236 KB Output is correct
65 Correct 245 ms 153864 KB Output is correct
66 Correct 249 ms 150672 KB Output is correct
67 Correct 160 ms 153048 KB Output is correct
68 Correct 164 ms 151020 KB Output is correct
69 Correct 166 ms 153048 KB Output is correct
70 Correct 157 ms 150444 KB Output is correct
71 Correct 153 ms 149352 KB Output is correct
72 Correct 152 ms 153784 KB Output is correct
73 Correct 148 ms 153304 KB Output is correct
74 Correct 149 ms 151908 KB Output is correct
75 Correct 125 ms 142040 KB Output is correct
76 Correct 128 ms 142352 KB Output is correct
77 Correct 129 ms 143600 KB Output is correct
78 Correct 155 ms 151720 KB Output is correct
79 Correct 150 ms 152096 KB Output is correct
80 Correct 1817 ms 1038916 KB Output is correct
81 Correct 1552 ms 1039936 KB Output is correct
82 Correct 1510 ms 1039652 KB Output is correct
83 Correct 1514 ms 1039396 KB Output is correct
84 Correct 1561 ms 1048576 KB Output is correct
85 Correct 1491 ms 1046800 KB Output is correct
86 Correct 1486 ms 1047568 KB Output is correct
87 Correct 1123 ms 1014580 KB Output is correct
88 Runtime error 1339 ms 1048576 KB Execution killed with signal 9
89 Halted 0 ms 0 KB -