oj.uz

Submission #975769

# Submission time Handle Problem Language Result Execution time Memory
975769 2024-05-05T20:14:51 Z starchan Port Facility (JOI17_port_facility) C++17
100 / 100
 2769 ms 625752 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+5e6;
const int mod = 1e9+7;
 
vector<int> g[SMX];

int lleft[LMX];
int rright[LMX];
int tree[LMX];
int nxt = 0;
 
int New()
{
	nxt++;
	lleft[nxt] = rright[nxt] = -1;
	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(const int &i, int pos, int id, int l, int r)
{
	int id_n;
	if(l == r)
		id_n = i;
	else
		id_n = New();
	tree[id_n] = 1;
	if(l == r)
		return id_n;
	lleft[id_n] = lleft[id]; rright[id_n] = rright[id];
	int m = (l+r)/2;
	if(pos <= m)
		lleft[id_n] = upd(i, pos, lleft[id], l, m);
	else
		rright[id_n] = upd(i, pos, rright[id], m+1, r);
	return id_n;
}
 
void add(const 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;
}
 
int pa[LMX]; bool col[LMX]; 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);
	for(int i = 0; i < n; i++)
		cin >> vv[i][0] >> vv[i][1];
	sort(vv.begin(), vv.end());
	nxt = n; int root = build(1, 2*n); //cout << "nxt = " << nxt << endl;

	for(int i = 0; i < n; i++)
	{
		lleft[i] = rright[i] = -1;
		root = upd(i, vv[i][1], root, 1, 2*n);
		add(i, vv[i][0], vv[i][1]-1, root, 1, 2*n);
		//cout << "b[sn] = " << b[sn] << endl;
	}
 
	int N = nxt; 
	for(int i = 0; i <= N; i++)
		pa[i] = -1;
	for(int i = 0; i < n; i++)
		dfs(i);
	if(!works)
	{
		cout << "0\n";
		return 0;
	}
	int ans = 1;
	for(int i = 0; i < n; i++)
	{
		if(ppl[leader(i)])
			continue;
		ppl[leader(i)] = 1; ans*=2; ans%=mod;
	}
	cout << ans << "\n";
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 35676 KB Output is correct
2 Correct 8 ms 35676 KB Output is correct
3 Correct 8 ms 35676 KB Output is correct
4 Correct 7 ms 35768 KB Output is correct
5 Correct 7 ms 35676 KB Output is correct
6 Correct 7 ms 35672 KB Output is correct
7 Correct 7 ms 35676 KB Output is correct
8 Correct 7 ms 35844 KB Output is correct
9 Correct 7 ms 35676 KB Output is correct
10 Correct 7 ms 35676 KB Output is correct
11 Correct 7 ms 35792 KB Output is correct
12 Correct 8 ms 35676 KB Output is correct
13 Correct 7 ms 35676 KB Output is correct
14 Correct 8 ms 35676 KB Output is correct
15 Correct 7 ms 35676 KB Output is correct
16 Correct 7 ms 35676 KB Output is correct
17 Correct 7 ms 35868 KB Output is correct
18 Correct 7 ms 35676 KB Output is correct
19 Correct 7 ms 35776 KB Output is correct
20 Correct 7 ms 35676 KB Output is correct
21 Correct 8 ms 35776 KB Output is correct
22 Correct 7 ms 35676 KB Output is correct
23 Correct 7 ms 35860 KB Output is correct
24 Correct 7 ms 35676 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 35676 KB Output is correct
2 Correct 8 ms 35676 KB Output is correct
3 Correct 8 ms 35676 KB Output is correct
4 Correct 7 ms 35768 KB Output is correct
5 Correct 7 ms 35676 KB Output is correct
6 Correct 7 ms 35672 KB Output is correct
7 Correct 7 ms 35676 KB Output is correct
8 Correct 7 ms 35844 KB Output is correct
9 Correct 7 ms 35676 KB Output is correct
10 Correct 7 ms 35676 KB Output is correct
11 Correct 7 ms 35792 KB Output is correct
12 Correct 8 ms 35676 KB Output is correct
13 Correct 7 ms 35676 KB Output is correct
14 Correct 8 ms 35676 KB Output is correct
15 Correct 7 ms 35676 KB Output is correct
16 Correct 7 ms 35676 KB Output is correct
17 Correct 7 ms 35868 KB Output is correct
18 Correct 7 ms 35676 KB Output is correct
19 Correct 7 ms 35776 KB Output is correct
20 Correct 7 ms 35676 KB Output is correct
21 Correct 8 ms 35776 KB Output is correct
22 Correct 7 ms 35676 KB Output is correct
23 Correct 7 ms 35860 KB Output is correct
24 Correct 7 ms 35676 KB Output is correct
25 Correct 9 ms 35932 KB Output is correct
26 Correct 9 ms 35932 KB Output is correct
27 Correct 8 ms 35932 KB Output is correct
28 Correct 9 ms 35932 KB Output is correct
29 Correct 10 ms 35932 KB Output is correct
30 Correct 8 ms 35932 KB Output is correct
31 Correct 9 ms 35792 KB Output is correct
32 Correct 8 ms 35932 KB Output is correct
33 Correct 8 ms 35932 KB Output is correct
34 Correct 9 ms 35932 KB Output is correct
35 Correct 8 ms 35932 KB Output is correct
36 Correct 9 ms 35800 KB Output is correct
37 Correct 8 ms 35932 KB Output is correct
38 Correct 8 ms 35932 KB Output is correct
39 Correct 8 ms 35932 KB Output is correct
40 Correct 7 ms 35932 KB Output is correct
41 Correct 9 ms 35932 KB Output is correct
42 Correct 10 ms 35932 KB Output is correct
43 Correct 8 ms 35932 KB Output is correct
44 Correct 8 ms 35928 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 35676 KB Output is correct
2 Correct 8 ms 35676 KB Output is correct
3 Correct 8 ms 35676 KB Output is correct
4 Correct 7 ms 35768 KB Output is correct
5 Correct 7 ms 35676 KB Output is correct
6 Correct 7 ms 35672 KB Output is correct
7 Correct 7 ms 35676 KB Output is correct
8 Correct 7 ms 35844 KB Output is correct
9 Correct 7 ms 35676 KB Output is correct
10 Correct 7 ms 35676 KB Output is correct
11 Correct 7 ms 35792 KB Output is correct
12 Correct 8 ms 35676 KB Output is correct
13 Correct 7 ms 35676 KB Output is correct
14 Correct 8 ms 35676 KB Output is correct
15 Correct 7 ms 35676 KB Output is correct
16 Correct 7 ms 35676 KB Output is correct
17 Correct 7 ms 35868 KB Output is correct
18 Correct 7 ms 35676 KB Output is correct
19 Correct 7 ms 35776 KB Output is correct
20 Correct 7 ms 35676 KB Output is correct
21 Correct 8 ms 35776 KB Output is correct
22 Correct 7 ms 35676 KB Output is correct
23 Correct 7 ms 35860 KB Output is correct
24 Correct 7 ms 35676 KB Output is correct
25 Correct 9 ms 35932 KB Output is correct
26 Correct 9 ms 35932 KB Output is correct
27 Correct 8 ms 35932 KB Output is correct
28 Correct 9 ms 35932 KB Output is correct
29 Correct 10 ms 35932 KB Output is correct
30 Correct 8 ms 35932 KB Output is correct
31 Correct 9 ms 35792 KB Output is correct
32 Correct 8 ms 35932 KB Output is correct
33 Correct 8 ms 35932 KB Output is correct
34 Correct 9 ms 35932 KB Output is correct
35 Correct 8 ms 35932 KB Output is correct
36 Correct 9 ms 35800 KB Output is correct
37 Correct 8 ms 35932 KB Output is correct
38 Correct 8 ms 35932 KB Output is correct
39 Correct 8 ms 35932 KB Output is correct
40 Correct 7 ms 35932 KB Output is correct
41 Correct 9 ms 35932 KB Output is correct
42 Correct 10 ms 35932 KB Output is correct
43 Correct 8 ms 35932 KB Output is correct
44 Correct 8 ms 35928 KB Output is correct
45 Correct 115 ms 80956 KB Output is correct
46 Correct 105 ms 80904 KB Output is correct
47 Correct 95 ms 80976 KB Output is correct
48 Correct 97 ms 80920 KB Output is correct
49 Correct 100 ms 81136 KB Output is correct
50 Correct 96 ms 80720 KB Output is correct
51 Correct 96 ms 80696 KB Output is correct
52 Correct 61 ms 74580 KB Output is correct
53 Correct 89 ms 82516 KB Output is correct
54 Correct 113 ms 85304 KB Output is correct
55 Correct 99 ms 82800 KB Output is correct
56 Correct 117 ms 83228 KB Output is correct
57 Correct 68 ms 75076 KB Output is correct
58 Correct 62 ms 74840 KB Output is correct
59 Correct 77 ms 78676 KB Output is correct
60 Correct 86 ms 79184 KB Output is correct
61 Correct 91 ms 79440 KB Output is correct
62 Correct 80 ms 78416 KB Output is correct
63 Correct 88 ms 78964 KB Output is correct
64 Correct 89 ms 79184 KB Output is correct
65 Correct 176 ms 83792 KB Output is correct
66 Correct 176 ms 83792 KB Output is correct
67 Correct 99 ms 82968 KB Output is correct
68 Correct 98 ms 83024 KB Output is correct
69 Correct 105 ms 82768 KB Output is correct
70 Correct 98 ms 82636 KB Output is correct
71 Correct 93 ms 83472 KB Output is correct
72 Correct 96 ms 83536 KB Output is correct
73 Correct 93 ms 83140 KB Output is correct
74 Correct 93 ms 83112 KB Output is correct
75 Correct 77 ms 76368 KB Output is correct
76 Correct 67 ms 76364 KB Output is correct
77 Correct 69 ms 76332 KB Output is correct
78 Correct 104 ms 81420 KB Output is correct
79 Correct 96 ms 81072 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 35676 KB Output is correct
2 Correct 8 ms 35676 KB Output is correct
3 Correct 8 ms 35676 KB Output is correct
4 Correct 7 ms 35768 KB Output is correct
5 Correct 7 ms 35676 KB Output is correct
6 Correct 7 ms 35672 KB Output is correct
7 Correct 7 ms 35676 KB Output is correct
8 Correct 7 ms 35844 KB Output is correct
9 Correct 7 ms 35676 KB Output is correct
10 Correct 7 ms 35676 KB Output is correct
11 Correct 7 ms 35792 KB Output is correct
12 Correct 8 ms 35676 KB Output is correct
13 Correct 7 ms 35676 KB Output is correct
14 Correct 8 ms 35676 KB Output is correct
15 Correct 7 ms 35676 KB Output is correct
16 Correct 7 ms 35676 KB Output is correct
17 Correct 7 ms 35868 KB Output is correct
18 Correct 7 ms 35676 KB Output is correct
19 Correct 7 ms 35776 KB Output is correct
20 Correct 7 ms 35676 KB Output is correct
21 Correct 8 ms 35776 KB Output is correct
22 Correct 7 ms 35676 KB Output is correct
23 Correct 7 ms 35860 KB Output is correct
24 Correct 7 ms 35676 KB Output is correct
25 Correct 9 ms 35932 KB Output is correct
26 Correct 9 ms 35932 KB Output is correct
27 Correct 8 ms 35932 KB Output is correct
28 Correct 9 ms 35932 KB Output is correct
29 Correct 10 ms 35932 KB Output is correct
30 Correct 8 ms 35932 KB Output is correct
31 Correct 9 ms 35792 KB Output is correct
32 Correct 8 ms 35932 KB Output is correct
33 Correct 8 ms 35932 KB Output is correct
34 Correct 9 ms 35932 KB Output is correct
35 Correct 8 ms 35932 KB Output is correct
36 Correct 9 ms 35800 KB Output is correct
37 Correct 8 ms 35932 KB Output is correct
38 Correct 8 ms 35932 KB Output is correct
39 Correct 8 ms 35932 KB Output is correct
40 Correct 7 ms 35932 KB Output is correct
41 Correct 9 ms 35932 KB Output is correct
42 Correct 10 ms 35932 KB Output is correct
43 Correct 8 ms 35932 KB Output is correct
44 Correct 8 ms 35928 KB Output is correct
45 Correct 115 ms 80956 KB Output is correct
46 Correct 105 ms 80904 KB Output is correct
47 Correct 95 ms 80976 KB Output is correct
48 Correct 97 ms 80920 KB Output is correct
49 Correct 100 ms 81136 KB Output is correct
50 Correct 96 ms 80720 KB Output is correct
51 Correct 96 ms 80696 KB Output is correct
52 Correct 61 ms 74580 KB Output is correct
53 Correct 89 ms 82516 KB Output is correct
54 Correct 113 ms 85304 KB Output is correct
55 Correct 99 ms 82800 KB Output is correct
56 Correct 117 ms 83228 KB Output is correct
57 Correct 68 ms 75076 KB Output is correct
58 Correct 62 ms 74840 KB Output is correct
59 Correct 77 ms 78676 KB Output is correct
60 Correct 86 ms 79184 KB Output is correct
61 Correct 91 ms 79440 KB Output is correct
62 Correct 80 ms 78416 KB Output is correct
63 Correct 88 ms 78964 KB Output is correct
64 Correct 89 ms 79184 KB Output is correct
65 Correct 176 ms 83792 KB Output is correct
66 Correct 176 ms 83792 KB Output is correct
67 Correct 99 ms 82968 KB Output is correct
68 Correct 98 ms 83024 KB Output is correct
69 Correct 105 ms 82768 KB Output is correct
70 Correct 98 ms 82636 KB Output is correct
71 Correct 93 ms 83472 KB Output is correct
72 Correct 96 ms 83536 KB Output is correct
73 Correct 93 ms 83140 KB Output is correct
74 Correct 93 ms 83112 KB Output is correct
75 Correct 77 ms 76368 KB Output is correct
76 Correct 67 ms 76364 KB Output is correct
77 Correct 69 ms 76332 KB Output is correct
78 Correct 104 ms 81420 KB Output is correct
79 Correct 96 ms 81072 KB Output is correct
80 Correct 1163 ms 558468 KB Output is correct
81 Correct 1027 ms 558672 KB Output is correct
82 Correct 1033 ms 558728 KB Output is correct
83 Correct 1061 ms 558780 KB Output is correct
84 Correct 1087 ms 559696 KB Output is correct
85 Correct 1031 ms 556064 KB Output is correct
86 Correct 1030 ms 556168 KB Output is correct
87 Correct 599 ms 481224 KB Output is correct
88 Correct 923 ms 592532 KB Output is correct
89 Correct 1093 ms 625752 KB Output is correct
90 Correct 1121 ms 624872 KB Output is correct
91 Correct 1101 ms 624096 KB Output is correct
92 Correct 668 ms 500464 KB Output is correct
93 Correct 651 ms 495804 KB Output is correct
94 Correct 855 ms 554064 KB Output is correct
95 Correct 925 ms 555860 KB Output is correct
96 Correct 954 ms 560464 KB Output is correct
97 Correct 847 ms 551032 KB Output is correct
98 Correct 919 ms 553248 KB Output is correct
99 Correct 987 ms 557260 KB Output is correct
100 Correct 2769 ms 617180 KB Output is correct
101 Correct 2733 ms 617324 KB Output is correct
102 Correct 1063 ms 603216 KB Output is correct
103 Correct 1096 ms 603456 KB Output is correct
104 Correct 1067 ms 601232 KB Output is correct
105 Correct 1070 ms 600840 KB Output is correct
106 Correct 995 ms 604808 KB Output is correct
107 Correct 1043 ms 603880 KB Output is correct
108 Correct 966 ms 606544 KB Output is correct
109 Correct 1000 ms 606372 KB Output is correct
110 Correct 683 ms 518412 KB Output is correct
111 Correct 686 ms 518228 KB Output is correct
112 Correct 666 ms 518388 KB Output is correct
113 Correct 1034 ms 573060 KB Output is correct
114 Correct 1004 ms 573028 KB Output is correct