Submission #975742

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
975742	2024-05-05T19:55:49 Z	starchan	Port Facility (JOI17_port_facility)	C++17	78 / 100	931 ms	1048576 KB

port_facility

#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<int> g[LMX];
 
int leaf[MX]; 
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(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;
}
 
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+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 = nxt; 
	for(int i = 1; i <= N; i++)
		pa[i] = -1;
	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

#	Verdict	Execution time	Memory	Grader output
1	Correct	360 ms	716268 KB	Output is correct
2	Correct	155 ms	716112 KB	Output is correct
3	Correct	166 ms	716212 KB	Output is correct
4	Correct	155 ms	716184 KB	Output is correct
5	Correct	157 ms	716172 KB	Output is correct
6	Correct	154 ms	716040 KB	Output is correct
7	Correct	157 ms	716112 KB	Output is correct
8	Correct	157 ms	716304 KB	Output is correct
9	Correct	158 ms	716112 KB	Output is correct
10	Correct	157 ms	716220 KB	Output is correct
11	Correct	163 ms	716220 KB	Output is correct
12	Correct	156 ms	716044 KB	Output is correct
13	Correct	158 ms	716116 KB	Output is correct
14	Correct	163 ms	716112 KB	Output is correct
15	Correct	161 ms	716208 KB	Output is correct
16	Correct	160 ms	716216 KB	Output is correct
17	Correct	157 ms	716224 KB	Output is correct
18	Correct	155 ms	716004 KB	Output is correct
19	Correct	158 ms	716212 KB	Output is correct
20	Correct	166 ms	716052 KB	Output is correct
21	Correct	165 ms	716112 KB	Output is correct
22	Correct	161 ms	716276 KB	Output is correct
23	Correct	159 ms	716212 KB	Output is correct
24	Correct	159 ms	716116 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	360 ms	716268 KB	Output is correct
2	Correct	155 ms	716112 KB	Output is correct
3	Correct	166 ms	716212 KB	Output is correct
4	Correct	155 ms	716184 KB	Output is correct
5	Correct	157 ms	716172 KB	Output is correct
6	Correct	154 ms	716040 KB	Output is correct
7	Correct	157 ms	716112 KB	Output is correct
8	Correct	157 ms	716304 KB	Output is correct
9	Correct	158 ms	716112 KB	Output is correct
10	Correct	157 ms	716220 KB	Output is correct
11	Correct	163 ms	716220 KB	Output is correct
12	Correct	156 ms	716044 KB	Output is correct
13	Correct	158 ms	716116 KB	Output is correct
14	Correct	163 ms	716112 KB	Output is correct
15	Correct	161 ms	716208 KB	Output is correct
16	Correct	160 ms	716216 KB	Output is correct
17	Correct	157 ms	716224 KB	Output is correct
18	Correct	155 ms	716004 KB	Output is correct
19	Correct	158 ms	716212 KB	Output is correct
20	Correct	166 ms	716052 KB	Output is correct
21	Correct	165 ms	716112 KB	Output is correct
22	Correct	161 ms	716276 KB	Output is correct
23	Correct	159 ms	716212 KB	Output is correct
24	Correct	159 ms	716116 KB	Output is correct
25	Correct	161 ms	716628 KB	Output is correct
26	Correct	159 ms	716512 KB	Output is correct
27	Correct	166 ms	716516 KB	Output is correct
28	Correct	180 ms	716464 KB	Output is correct
29	Correct	166 ms	716604 KB	Output is correct
30	Correct	159 ms	716436 KB	Output is correct
31	Correct	160 ms	716372 KB	Output is correct
32	Correct	164 ms	716384 KB	Output is correct
33	Correct	158 ms	716368 KB	Output is correct
34	Correct	164 ms	716508 KB	Output is correct
35	Correct	163 ms	716644 KB	Output is correct
36	Correct	158 ms	716368 KB	Output is correct
37	Correct	177 ms	716372 KB	Output is correct
38	Correct	160 ms	716624 KB	Output is correct
39	Correct	158 ms	716464 KB	Output is correct
40	Correct	156 ms	716368 KB	Output is correct
41	Correct	158 ms	716368 KB	Output is correct
42	Correct	169 ms	716308 KB	Output is correct
43	Correct	161 ms	716368 KB	Output is correct
44	Correct	159 ms	716352 KB	Output is correct

Subtask #3
56.0 / 56.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	360 ms	716268 KB	Output is correct
2	Correct	155 ms	716112 KB	Output is correct
3	Correct	166 ms	716212 KB	Output is correct
4	Correct	155 ms	716184 KB	Output is correct
5	Correct	157 ms	716172 KB	Output is correct
6	Correct	154 ms	716040 KB	Output is correct
7	Correct	157 ms	716112 KB	Output is correct
8	Correct	157 ms	716304 KB	Output is correct
9	Correct	158 ms	716112 KB	Output is correct
10	Correct	157 ms	716220 KB	Output is correct
11	Correct	163 ms	716220 KB	Output is correct
12	Correct	156 ms	716044 KB	Output is correct
13	Correct	158 ms	716116 KB	Output is correct
14	Correct	163 ms	716112 KB	Output is correct
15	Correct	161 ms	716208 KB	Output is correct
16	Correct	160 ms	716216 KB	Output is correct
17	Correct	157 ms	716224 KB	Output is correct
18	Correct	155 ms	716004 KB	Output is correct
19	Correct	158 ms	716212 KB	Output is correct
20	Correct	166 ms	716052 KB	Output is correct
21	Correct	165 ms	716112 KB	Output is correct
22	Correct	161 ms	716276 KB	Output is correct
23	Correct	159 ms	716212 KB	Output is correct
24	Correct	159 ms	716116 KB	Output is correct
25	Correct	161 ms	716628 KB	Output is correct
26	Correct	159 ms	716512 KB	Output is correct
27	Correct	166 ms	716516 KB	Output is correct
28	Correct	180 ms	716464 KB	Output is correct
29	Correct	166 ms	716604 KB	Output is correct
30	Correct	159 ms	716436 KB	Output is correct
31	Correct	160 ms	716372 KB	Output is correct
32	Correct	164 ms	716384 KB	Output is correct
33	Correct	158 ms	716368 KB	Output is correct
34	Correct	164 ms	716508 KB	Output is correct
35	Correct	163 ms	716644 KB	Output is correct
36	Correct	158 ms	716368 KB	Output is correct
37	Correct	177 ms	716372 KB	Output is correct
38	Correct	160 ms	716624 KB	Output is correct
39	Correct	158 ms	716464 KB	Output is correct
40	Correct	156 ms	716368 KB	Output is correct
41	Correct	158 ms	716368 KB	Output is correct
42	Correct	169 ms	716308 KB	Output is correct
43	Correct	161 ms	716368 KB	Output is correct
44	Correct	159 ms	716352 KB	Output is correct
45	Correct	285 ms	766024 KB	Output is correct
46	Correct	266 ms	765780 KB	Output is correct
47	Correct	267 ms	765780 KB	Output is correct
48	Correct	259 ms	765780 KB	Output is correct
49	Correct	256 ms	765900 KB	Output is correct
50	Correct	255 ms	765548 KB	Output is correct
51	Correct	255 ms	765524 KB	Output is correct
52	Correct	216 ms	759712 KB	Output is correct
53	Correct	250 ms	767408 KB	Output is correct
54	Correct	263 ms	770128 KB	Output is correct
55	Correct	262 ms	767624 KB	Output is correct
56	Correct	262 ms	768016 KB	Output is correct
57	Correct	238 ms	761428 KB	Output is correct
58	Correct	222 ms	759492 KB	Output is correct
59	Correct	243 ms	764064 KB	Output is correct
60	Correct	251 ms	764196 KB	Output is correct
61	Correct	248 ms	764348 KB	Output is correct
62	Correct	239 ms	763988 KB	Output is correct
63	Correct	250 ms	764036 KB	Output is correct
64	Correct	255 ms	764188 KB	Output is correct
65	Correct	338 ms	768848 KB	Output is correct
66	Correct	357 ms	769108 KB	Output is correct
67	Correct	263 ms	768808 KB	Output is correct
68	Correct	267 ms	768828 KB	Output is correct
69	Correct	270 ms	768568 KB	Output is correct
70	Correct	261 ms	768596 KB	Output is correct
71	Correct	294 ms	769184 KB	Output is correct
72	Correct	256 ms	769264 KB	Output is correct
73	Correct	276 ms	769284 KB	Output is correct
74	Correct	259 ms	769104 KB	Output is correct
75	Correct	236 ms	761168 KB	Output is correct
76	Correct	228 ms	761168 KB	Output is correct
77	Correct	227 ms	761172 KB	Output is correct
78	Correct	258 ms	766220 KB	Output is correct
79	Correct	255 ms	765848 KB	Output is correct

Subtask #4
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	360 ms	716268 KB	Output is correct
2	Correct	155 ms	716112 KB	Output is correct
3	Correct	166 ms	716212 KB	Output is correct
4	Correct	155 ms	716184 KB	Output is correct
5	Correct	157 ms	716172 KB	Output is correct
6	Correct	154 ms	716040 KB	Output is correct
7	Correct	157 ms	716112 KB	Output is correct
8	Correct	157 ms	716304 KB	Output is correct
9	Correct	158 ms	716112 KB	Output is correct
10	Correct	157 ms	716220 KB	Output is correct
11	Correct	163 ms	716220 KB	Output is correct
12	Correct	156 ms	716044 KB	Output is correct
13	Correct	158 ms	716116 KB	Output is correct
14	Correct	163 ms	716112 KB	Output is correct
15	Correct	161 ms	716208 KB	Output is correct
16	Correct	160 ms	716216 KB	Output is correct
17	Correct	157 ms	716224 KB	Output is correct
18	Correct	155 ms	716004 KB	Output is correct
19	Correct	158 ms	716212 KB	Output is correct
20	Correct	166 ms	716052 KB	Output is correct
21	Correct	165 ms	716112 KB	Output is correct
22	Correct	161 ms	716276 KB	Output is correct
23	Correct	159 ms	716212 KB	Output is correct
24	Correct	159 ms	716116 KB	Output is correct
25	Correct	161 ms	716628 KB	Output is correct
26	Correct	159 ms	716512 KB	Output is correct
27	Correct	166 ms	716516 KB	Output is correct
28	Correct	180 ms	716464 KB	Output is correct
29	Correct	166 ms	716604 KB	Output is correct
30	Correct	159 ms	716436 KB	Output is correct
31	Correct	160 ms	716372 KB	Output is correct
32	Correct	164 ms	716384 KB	Output is correct
33	Correct	158 ms	716368 KB	Output is correct
34	Correct	164 ms	716508 KB	Output is correct
35	Correct	163 ms	716644 KB	Output is correct
36	Correct	158 ms	716368 KB	Output is correct
37	Correct	177 ms	716372 KB	Output is correct
38	Correct	160 ms	716624 KB	Output is correct
39	Correct	158 ms	716464 KB	Output is correct
40	Correct	156 ms	716368 KB	Output is correct
41	Correct	158 ms	716368 KB	Output is correct
42	Correct	169 ms	716308 KB	Output is correct
43	Correct	161 ms	716368 KB	Output is correct
44	Correct	159 ms	716352 KB	Output is correct
45	Correct	285 ms	766024 KB	Output is correct
46	Correct	266 ms	765780 KB	Output is correct
47	Correct	267 ms	765780 KB	Output is correct
48	Correct	259 ms	765780 KB	Output is correct
49	Correct	256 ms	765900 KB	Output is correct
50	Correct	255 ms	765548 KB	Output is correct
51	Correct	255 ms	765524 KB	Output is correct
52	Correct	216 ms	759712 KB	Output is correct
53	Correct	250 ms	767408 KB	Output is correct
54	Correct	263 ms	770128 KB	Output is correct
55	Correct	262 ms	767624 KB	Output is correct
56	Correct	262 ms	768016 KB	Output is correct
57	Correct	238 ms	761428 KB	Output is correct
58	Correct	222 ms	759492 KB	Output is correct
59	Correct	243 ms	764064 KB	Output is correct
60	Correct	251 ms	764196 KB	Output is correct
61	Correct	248 ms	764348 KB	Output is correct
62	Correct	239 ms	763988 KB	Output is correct
63	Correct	250 ms	764036 KB	Output is correct
64	Correct	255 ms	764188 KB	Output is correct
65	Correct	338 ms	768848 KB	Output is correct
66	Correct	357 ms	769108 KB	Output is correct
67	Correct	263 ms	768808 KB	Output is correct
68	Correct	267 ms	768828 KB	Output is correct
69	Correct	270 ms	768568 KB	Output is correct
70	Correct	261 ms	768596 KB	Output is correct
71	Correct	294 ms	769184 KB	Output is correct
72	Correct	256 ms	769264 KB	Output is correct
73	Correct	276 ms	769284 KB	Output is correct
74	Correct	259 ms	769104 KB	Output is correct
75	Correct	236 ms	761168 KB	Output is correct
76	Correct	228 ms	761168 KB	Output is correct
77	Correct	227 ms	761172 KB	Output is correct
78	Correct	258 ms	766220 KB	Output is correct
79	Correct	255 ms	765848 KB	Output is correct
80	Runtime error	931 ms	1048576 KB	Execution killed with signal 9
81	Halted	0 ms	0 KB	-

Submission #975742

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 56.0 / 56.0

Subtask #4 0 / 22.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
56.0 / 56.0

Subtask #4
0 / 22.0