답안 #489552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
489552	2021-11-23T07:46:20 Z	cpp219	The short shank; Redemption (BOI21_prison)	C++14	100 / 100	1521 ms	318100 KB

prison

#include <algorithm>
#include <numeric>
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cassert>
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
const int maxn = 2e6+10;
 
int n, D, T;
 
vector<int> kids[maxn];
int stme[maxn];
int tmi[maxn];
int frit[maxn];
int par[maxn];
int init[maxn];
bool vis[maxn];
int tin[maxn];
int tout[maxn];
int inord[maxn];
int timer = 0;
 
struct seg
{
	int l, r;
	inline bool operator<(seg& b)
	{
		return l < b.l  or (l == b.l and r > b.r);
	}
	inline bool in(seg& b)
	{
		return b.l <= l and r <= b.r;
	}
} segs[maxn];
 
void dfs(int v, int h)
{
	init[v] = h;
	tin[v] = timer++;
	inord[tin[v]] = v;
	for(int u: kids[v])
		dfs(u, h+1);
	tout[v] = timer;
}
 
struct lzst
{
	vector<int> vals; // max
	vector<int> vidx; // max index
	vector<int> lazy;
	int n;
	lzst(int len)
	{
		vals = vector<int>(len * 4, 0);
		vidx = vector<int>(len * 4, 0);
		lazy = vector<int>(len * 4, 0);
		n = len;
		build(0, len, 1);
	}
	inline void upd(int v)
	{
		vals[v] = max(vals[2*v], vals[2*v+1]);
		if(vals[v] == vals[2*v])
			vidx[v] = vidx[2*v];
		else
			vidx[v] = vidx[2*v+1];
	}
	inline void put(int x, int v)
	{
		vals[v] += x;
		lazy[v] += x;
	}
	inline void shift(int v)
	{
		if(lazy[v] == 0) return;
		put(lazy[v], 2*v);
		put(lazy[v], 2*v+1);
		lazy[v] = 0;
	}
	void build(int l, int r, int v)
	{
		if(r - l == 1)
		{
			vals[v] = init[inord[l]];
			vidx[v] = inord[l];
			lazy[v] = 0;
			return;
		}
		int m = (l+r) / 2;
		build(l, m, 2*v);
		build(m, r, 2*v+1);
		upd(v);
	}
	void _add(int l, int r, int s, int e, int x, int v)
	{
		if(e <= l or r <= s) return;
		if(s <= l and r <= e) return put(x, v);
		int m = (l+r) / 2;
		shift(v);
		_add(l, m, s, e, x, 2*v);
		_add(m, r, s, e, x, 2*v+1);
		upd(v);
	}
	inline void add(int s, int e, int x)
	{
		_add(0, n, s, e, x, 1);
	}
};
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> D >> T;
	stack<int> st;
	int scnt = 0;
	segs[scnt++] = {0, n};
	int rem = n+1;
	for(int i = 0; i < n; i++)
	{
		cin >> stme[i];
		tmi[i] = stme[i] - i;
		st.push(i);
		while(!st.empty() and tmi[st.top()] > T-i)
			st.pop();
		if(st.empty())
		{
			frit[i] = i;
			rem--;
		}
		else
			frit[i] = st.top();
		if(frit[i] != i)
			segs[scnt++] = {frit[i], i};
		//cerr << "frit[" << i << "]: " << frit[i] << endl;
	}
	sort(segs, segs+scnt);
	//for(int i = 0; i < scnt; i++) cerr << i << ": " << segs[i].l << " " << segs[i].r << endl; cerr << endl;
	int lst = 0;
	par[0] = -1;
	for(int i = 1; i < scnt; i++)
	{
		while(!segs[i].in(segs[lst]))
			lst = par[lst];
		par[i] = lst;
		kids[lst].push_back(i);
		lst = i;
		//cerr << "par[" << i << "]: " << par[i] << endl;
	}
	dfs(0, 1);
	//for(int i = 0; i < scnt; i++) assert(tin[i] == i);
	lzst mf(scnt);
	//cerr << rem << endl;
	//for(int i = 0; i < 15; i++) cerr << mf.vals[i] << " "; cerr << endl << endl;
	while(D--)
	{
		int v = mf.vidx[1];
		//cerr << v << endl;
		while(v != -1 and !vis[v])
		{
			mf.add(tin[v], tout[v], -1);
			vis[v] = true;
			rem--;
			v = par[v];
		}
	}
	cout << rem << endl;
	return 0;
}

Subtask #1

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	47308 KB	Output is correct
2	Correct	24 ms	47260 KB	Output is correct
3	Correct	24 ms	47308 KB	Output is correct
4	Correct	23 ms	47352 KB	Output is correct
5	Correct	25 ms	47368 KB	Output is correct
6	Correct	25 ms	47308 KB	Output is correct
7	Correct	24 ms	47308 KB	Output is correct
8	Correct	23 ms	47308 KB	Output is correct
9	Correct	25 ms	47372 KB	Output is correct
10	Correct	26 ms	47364 KB	Output is correct
11	Correct	31 ms	47384 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	47292 KB	Output is correct
2	Correct	108 ms	77232 KB	Output is correct
3	Correct	95 ms	69452 KB	Output is correct
4	Correct	151 ms	80272 KB	Output is correct
5	Correct	101 ms	85412 KB	Output is correct
6	Correct	127 ms	75132 KB	Output is correct
7	Correct	508 ms	129860 KB	Output is correct
8	Correct	128 ms	79548 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	47308 KB	Output is correct
2	Correct	24 ms	47260 KB	Output is correct
3	Correct	24 ms	47308 KB	Output is correct
4	Correct	23 ms	47352 KB	Output is correct
5	Correct	25 ms	47368 KB	Output is correct
6	Correct	25 ms	47308 KB	Output is correct
7	Correct	24 ms	47308 KB	Output is correct
8	Correct	23 ms	47308 KB	Output is correct
9	Correct	25 ms	47372 KB	Output is correct
10	Correct	26 ms	47364 KB	Output is correct
11	Correct	31 ms	47384 KB	Output is correct
12	Correct	24 ms	47340 KB	Output is correct
13	Correct	24 ms	47384 KB	Output is correct
14	Correct	25 ms	47280 KB	Output is correct
15	Correct	25 ms	47308 KB	Output is correct
16	Correct	32 ms	47352 KB	Output is correct
17	Correct	25 ms	47368 KB	Output is correct
18	Correct	28 ms	47300 KB	Output is correct
19	Correct	24 ms	47308 KB	Output is correct
20	Correct	25 ms	47332 KB	Output is correct
21	Correct	25 ms	47308 KB	Output is correct
22	Correct	24 ms	47364 KB	Output is correct
23	Correct	25 ms	47560 KB	Output is correct
24	Correct	26 ms	47468 KB	Output is correct
25	Correct	32 ms	47552 KB	Output is correct
26	Correct	29 ms	47564 KB	Output is correct
27	Correct	25 ms	47544 KB	Output is correct
28	Correct	25 ms	47564 KB	Output is correct
29	Correct	24 ms	47528 KB	Output is correct
30	Correct	25 ms	47584 KB	Output is correct
31	Correct	26 ms	47568 KB	Output is correct
32	Correct	26 ms	47524 KB	Output is correct
33	Correct	25 ms	47564 KB	Output is correct
34	Correct	25 ms	47632 KB	Output is correct
35	Correct	26 ms	47564 KB	Output is correct

Subtask #4

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	47216 KB	Output is correct
2	Correct	48 ms	52784 KB	Output is correct
3	Correct	38 ms	51884 KB	Output is correct
4	Correct	48 ms	55036 KB	Output is correct
5	Correct	55 ms	56088 KB	Output is correct
6	Correct	54 ms	56388 KB	Output is correct
7	Correct	39 ms	51396 KB	Output is correct
8	Correct	42 ms	51060 KB	Output is correct
9	Correct	80 ms	59656 KB	Output is correct
10	Correct	35 ms	51020 KB	Output is correct

Subtask #5

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	47308 KB	Output is correct
2	Correct	24 ms	47260 KB	Output is correct
3	Correct	24 ms	47308 KB	Output is correct
4	Correct	23 ms	47352 KB	Output is correct
5	Correct	25 ms	47368 KB	Output is correct
6	Correct	25 ms	47308 KB	Output is correct
7	Correct	24 ms	47308 KB	Output is correct
8	Correct	23 ms	47308 KB	Output is correct
9	Correct	25 ms	47372 KB	Output is correct
10	Correct	26 ms	47364 KB	Output is correct
11	Correct	31 ms	47384 KB	Output is correct
12	Correct	24 ms	47340 KB	Output is correct
13	Correct	24 ms	47384 KB	Output is correct
14	Correct	25 ms	47280 KB	Output is correct
15	Correct	25 ms	47308 KB	Output is correct
16	Correct	32 ms	47352 KB	Output is correct
17	Correct	25 ms	47368 KB	Output is correct
18	Correct	28 ms	47300 KB	Output is correct
19	Correct	24 ms	47308 KB	Output is correct
20	Correct	25 ms	47332 KB	Output is correct
21	Correct	25 ms	47308 KB	Output is correct
22	Correct	24 ms	47364 KB	Output is correct
23	Correct	25 ms	47560 KB	Output is correct
24	Correct	26 ms	47468 KB	Output is correct
25	Correct	32 ms	47552 KB	Output is correct
26	Correct	29 ms	47564 KB	Output is correct
27	Correct	25 ms	47544 KB	Output is correct
28	Correct	25 ms	47564 KB	Output is correct
29	Correct	24 ms	47528 KB	Output is correct
30	Correct	25 ms	47584 KB	Output is correct
31	Correct	26 ms	47568 KB	Output is correct
32	Correct	26 ms	47524 KB	Output is correct
33	Correct	25 ms	47564 KB	Output is correct
34	Correct	25 ms	47632 KB	Output is correct
35	Correct	26 ms	47564 KB	Output is correct
36	Correct	27 ms	47216 KB	Output is correct
37	Correct	48 ms	52784 KB	Output is correct
38	Correct	38 ms	51884 KB	Output is correct
39	Correct	48 ms	55036 KB	Output is correct
40	Correct	55 ms	56088 KB	Output is correct
41	Correct	54 ms	56388 KB	Output is correct
42	Correct	39 ms	51396 KB	Output is correct
43	Correct	42 ms	51060 KB	Output is correct
44	Correct	80 ms	59656 KB	Output is correct
45	Correct	35 ms	51020 KB	Output is correct
46	Correct	23 ms	47268 KB	Output is correct
47	Correct	25 ms	47376 KB	Output is correct
48	Correct	26 ms	47308 KB	Output is correct
49	Correct	25 ms	47320 KB	Output is correct
50	Correct	25 ms	47344 KB	Output is correct
51	Correct	31 ms	47300 KB	Output is correct
52	Correct	30 ms	47308 KB	Output is correct
53	Correct	26 ms	47312 KB	Output is correct
54	Correct	25 ms	47360 KB	Output is correct
55	Correct	24 ms	47308 KB	Output is correct
56	Correct	24 ms	47308 KB	Output is correct
57	Correct	27 ms	47552 KB	Output is correct
58	Correct	26 ms	47552 KB	Output is correct
59	Correct	26 ms	47688 KB	Output is correct
60	Correct	26 ms	47564 KB	Output is correct
61	Correct	26 ms	47580 KB	Output is correct
62	Correct	33 ms	47600 KB	Output is correct
63	Correct	26 ms	47580 KB	Output is correct
64	Correct	27 ms	47492 KB	Output is correct
65	Correct	26 ms	47536 KB	Output is correct
66	Correct	24 ms	47436 KB	Output is correct
67	Correct	25 ms	47540 KB	Output is correct
68	Correct	29 ms	47588 KB	Output is correct
69	Correct	26 ms	47612 KB	Output is correct
70	Correct	27 ms	47308 KB	Output is correct
71	Correct	39 ms	52828 KB	Output is correct
72	Correct	39 ms	51916 KB	Output is correct
73	Correct	64 ms	55012 KB	Output is correct
74	Correct	53 ms	56076 KB	Output is correct
75	Correct	54 ms	56364 KB	Output is correct
76	Correct	38 ms	51532 KB	Output is correct
77	Correct	39 ms	51116 KB	Output is correct
78	Correct	81 ms	59816 KB	Output is correct
79	Correct	34 ms	50968 KB	Output is correct
80	Correct	45 ms	51780 KB	Output is correct
81	Correct	65 ms	52832 KB	Output is correct
82	Correct	54 ms	51804 KB	Output is correct
83	Correct	60 ms	54260 KB	Output is correct
84	Correct	53 ms	52948 KB	Output is correct
85	Correct	57 ms	56940 KB	Output is correct
86	Correct	58 ms	53124 KB	Output is correct
87	Correct	46 ms	50956 KB	Output is correct
88	Correct	73 ms	57572 KB	Output is correct
89	Correct	72 ms	59276 KB	Output is correct
90	Correct	68 ms	56608 KB	Output is correct

Subtask #6

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	47308 KB	Output is correct
2	Correct	24 ms	47260 KB	Output is correct
3	Correct	24 ms	47308 KB	Output is correct
4	Correct	23 ms	47352 KB	Output is correct
5	Correct	25 ms	47368 KB	Output is correct
6	Correct	25 ms	47308 KB	Output is correct
7	Correct	24 ms	47308 KB	Output is correct
8	Correct	23 ms	47308 KB	Output is correct
9	Correct	25 ms	47372 KB	Output is correct
10	Correct	26 ms	47364 KB	Output is correct
11	Correct	31 ms	47384 KB	Output is correct
12	Correct	26 ms	47292 KB	Output is correct
13	Correct	108 ms	77232 KB	Output is correct
14	Correct	95 ms	69452 KB	Output is correct
15	Correct	151 ms	80272 KB	Output is correct
16	Correct	101 ms	85412 KB	Output is correct
17	Correct	127 ms	75132 KB	Output is correct
18	Correct	508 ms	129860 KB	Output is correct
19	Correct	128 ms	79548 KB	Output is correct
20	Correct	24 ms	47340 KB	Output is correct
21	Correct	24 ms	47384 KB	Output is correct
22	Correct	25 ms	47280 KB	Output is correct
23	Correct	25 ms	47308 KB	Output is correct
24	Correct	32 ms	47352 KB	Output is correct
25	Correct	25 ms	47368 KB	Output is correct
26	Correct	28 ms	47300 KB	Output is correct
27	Correct	24 ms	47308 KB	Output is correct
28	Correct	25 ms	47332 KB	Output is correct
29	Correct	25 ms	47308 KB	Output is correct
30	Correct	24 ms	47364 KB	Output is correct
31	Correct	25 ms	47560 KB	Output is correct
32	Correct	26 ms	47468 KB	Output is correct
33	Correct	32 ms	47552 KB	Output is correct
34	Correct	29 ms	47564 KB	Output is correct
35	Correct	25 ms	47544 KB	Output is correct
36	Correct	25 ms	47564 KB	Output is correct
37	Correct	24 ms	47528 KB	Output is correct
38	Correct	25 ms	47584 KB	Output is correct
39	Correct	26 ms	47568 KB	Output is correct
40	Correct	26 ms	47524 KB	Output is correct
41	Correct	25 ms	47564 KB	Output is correct
42	Correct	25 ms	47632 KB	Output is correct
43	Correct	26 ms	47564 KB	Output is correct
44	Correct	27 ms	47216 KB	Output is correct
45	Correct	48 ms	52784 KB	Output is correct
46	Correct	38 ms	51884 KB	Output is correct
47	Correct	48 ms	55036 KB	Output is correct
48	Correct	55 ms	56088 KB	Output is correct
49	Correct	54 ms	56388 KB	Output is correct
50	Correct	39 ms	51396 KB	Output is correct
51	Correct	42 ms	51060 KB	Output is correct
52	Correct	80 ms	59656 KB	Output is correct
53	Correct	35 ms	51020 KB	Output is correct
54	Correct	23 ms	47268 KB	Output is correct
55	Correct	25 ms	47376 KB	Output is correct
56	Correct	26 ms	47308 KB	Output is correct
57	Correct	25 ms	47320 KB	Output is correct
58	Correct	25 ms	47344 KB	Output is correct
59	Correct	31 ms	47300 KB	Output is correct
60	Correct	30 ms	47308 KB	Output is correct
61	Correct	26 ms	47312 KB	Output is correct
62	Correct	25 ms	47360 KB	Output is correct
63	Correct	24 ms	47308 KB	Output is correct
64	Correct	24 ms	47308 KB	Output is correct
65	Correct	27 ms	47552 KB	Output is correct
66	Correct	26 ms	47552 KB	Output is correct
67	Correct	26 ms	47688 KB	Output is correct
68	Correct	26 ms	47564 KB	Output is correct
69	Correct	26 ms	47580 KB	Output is correct
70	Correct	33 ms	47600 KB	Output is correct
71	Correct	26 ms	47580 KB	Output is correct
72	Correct	27 ms	47492 KB	Output is correct
73	Correct	26 ms	47536 KB	Output is correct
74	Correct	24 ms	47436 KB	Output is correct
75	Correct	25 ms	47540 KB	Output is correct
76	Correct	29 ms	47588 KB	Output is correct
77	Correct	26 ms	47612 KB	Output is correct
78	Correct	27 ms	47308 KB	Output is correct
79	Correct	39 ms	52828 KB	Output is correct
80	Correct	39 ms	51916 KB	Output is correct
81	Correct	64 ms	55012 KB	Output is correct
82	Correct	53 ms	56076 KB	Output is correct
83	Correct	54 ms	56364 KB	Output is correct
84	Correct	38 ms	51532 KB	Output is correct
85	Correct	39 ms	51116 KB	Output is correct
86	Correct	81 ms	59816 KB	Output is correct
87	Correct	34 ms	50968 KB	Output is correct
88	Correct	45 ms	51780 KB	Output is correct
89	Correct	65 ms	52832 KB	Output is correct
90	Correct	54 ms	51804 KB	Output is correct
91	Correct	60 ms	54260 KB	Output is correct
92	Correct	53 ms	52948 KB	Output is correct
93	Correct	57 ms	56940 KB	Output is correct
94	Correct	58 ms	53124 KB	Output is correct
95	Correct	46 ms	50956 KB	Output is correct
96	Correct	73 ms	57572 KB	Output is correct
97	Correct	72 ms	59276 KB	Output is correct
98	Correct	68 ms	56608 KB	Output is correct
99	Correct	24 ms	47308 KB	Output is correct
100	Correct	25 ms	47336 KB	Output is correct
101	Correct	25 ms	47348 KB	Output is correct
102	Correct	24 ms	47356 KB	Output is correct
103	Correct	26 ms	47436 KB	Output is correct
104	Correct	25 ms	47348 KB	Output is correct
105	Correct	24 ms	47308 KB	Output is correct
106	Correct	25 ms	47288 KB	Output is correct
107	Correct	24 ms	47308 KB	Output is correct
108	Correct	25 ms	47308 KB	Output is correct
109	Correct	25 ms	47372 KB	Output is correct
110	Correct	25 ms	47312 KB	Output is correct
111	Correct	108 ms	77172 KB	Output is correct
112	Correct	97 ms	69540 KB	Output is correct
113	Correct	123 ms	80484 KB	Output is correct
114	Correct	109 ms	85484 KB	Output is correct
115	Correct	158 ms	75100 KB	Output is correct
116	Correct	425 ms	129844 KB	Output is correct
117	Correct	147 ms	79524 KB	Output is correct
118	Correct	26 ms	47548 KB	Output is correct
119	Correct	27 ms	47516 KB	Output is correct
120	Correct	27 ms	47624 KB	Output is correct
121	Correct	25 ms	47556 KB	Output is correct
122	Correct	25 ms	47564 KB	Output is correct
123	Correct	25 ms	47548 KB	Output is correct
124	Correct	26 ms	47656 KB	Output is correct
125	Correct	27 ms	47484 KB	Output is correct
126	Correct	26 ms	47536 KB	Output is correct
127	Correct	26 ms	47416 KB	Output is correct
128	Correct	25 ms	47540 KB	Output is correct
129	Correct	32 ms	47588 KB	Output is correct
130	Correct	26 ms	47564 KB	Output is correct
131	Correct	27 ms	47248 KB	Output is correct
132	Correct	39 ms	52820 KB	Output is correct
133	Correct	38 ms	51868 KB	Output is correct
134	Correct	61 ms	55008 KB	Output is correct
135	Correct	59 ms	56072 KB	Output is correct
136	Correct	70 ms	56296 KB	Output is correct
137	Correct	39 ms	51420 KB	Output is correct
138	Correct	38 ms	51164 KB	Output is correct
139	Correct	85 ms	59736 KB	Output is correct
140	Correct	44 ms	51020 KB	Output is correct
141	Correct	42 ms	51904 KB	Output is correct
142	Correct	47 ms	52812 KB	Output is correct
143	Correct	58 ms	51852 KB	Output is correct
144	Correct	54 ms	54264 KB	Output is correct
145	Correct	49 ms	52956 KB	Output is correct
146	Correct	59 ms	56932 KB	Output is correct
147	Correct	52 ms	53120 KB	Output is correct
148	Correct	43 ms	50964 KB	Output is correct
149	Correct	71 ms	57560 KB	Output is correct
150	Correct	74 ms	59280 KB	Output is correct
151	Correct	74 ms	56636 KB	Output is correct
152	Correct	381 ms	167900 KB	Output is correct
153	Correct	418 ms	177716 KB	Output is correct
154	Correct	361 ms	160092 KB	Output is correct
155	Correct	781 ms	219880 KB	Output is correct
156	Correct	723 ms	208496 KB	Output is correct
157	Correct	324 ms	142544 KB	Output is correct
158	Correct	595 ms	188576 KB	Output is correct
159	Correct	1521 ms	318100 KB	Output is correct
160	Correct	1374 ms	301532 KB	Output is correct
161	Correct	534 ms	143848 KB	Output is correct
162	Correct	379 ms	147196 KB	Output is correct