oj.uz

Submission #952895

# Submission time Handle Problem Language Result Execution time Memory
952895 2024-03-25T04:44:02 Z tacocat The short shank; Redemption (BOI21_prison) C++14
80 / 100
 2000 ms 94424 KB 
/*
*       ___
*   _ /    _\_
*  / |    |___|
*  | |       |
*  \_|   __  |
*     \_/  \_/
*   uwu amogus
*/
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x7FFFFFFF
#define llinf 0x7FFFFFFFFFFFFFFF
#define ff first
#define ss second
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a - 1; i >= b; i--)
//#define assert void
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#define int ll
struct dsu {
	dsu(int n) {
		p.resize(n, -1);
		pp.resize(n); for (int i = 0; i < n; i++) pp[i] = i;
		r.resize(n, 0);
	}
	inline int par(int x) {
		return pp[_par(x)];
	}
	inline int _par(int x) {
		return p[x] == -1 ? x : p[x] = _par(p[x]);
	}
	inline void merge(int a, int b) {
		a = _par(a); b = _par(b);
		if (a == b)return;
		if (r[a] < r[b]) {
			swap(a, b);
			swap(pp[a], pp[b]);
		}
		if (r[a] == r[b]) r[a]++;
		p[b] = a;
	}
	vector<int> p, r, pp;
};
 
signed main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N, D, T; cin >> N >> D >> T;
	vector<int> t(N); for (auto& x : t) cin >> x;
	double l = 0, r = 2e6, m = 0;
	int ans = 0;
	for (int _ = 0; _ < 33; _++) {//aliens HAHAHAhaha ha ha :sob:
		m = (l + r) / 2;
		vector<pair<int,int>> st; st.reserve(N);
		struct node {
			int p = -1;//prev
			int n = -1;//next
			int lz = 0;
			double v = 0;
			int c = 0; // count owo!!!
			node() {};
			node(double v, int c) : v(v), c(c) {};
		};
		vector<node> st2; st2.reserve(N);
		dsu pls(N);
		int start = 0; 
		int amt = 0;//amount added
		function<void(int)> kill = [&](int i) {
			int n = st2[i].n;
			//assert(n != -1); 
			if (n == -1) return;
			if ((st2[i].v + (double)st2[i].lz > st2[n].v)) {
				int p = st2[i].p;
				st2[n].p = p;
				if (p != -1) {
					st2[p].lz += st2[i].lz;
					st2[p].n = n;
					pls.merge(p, i); //merge i to p
					kill(p);
				}
				else {
					// DEAD
					amt -= st2[i].lz; //recycle owo
					start = n;
				}
			}
		};
		for (int i = 0; i < N; i++) {
			//create and then upd
			if (st2.size()) {
				st2.push_back(node(st2[start].v + (double)amt + m, st2[start].c+1));
				st2[i - 1].n = i; st2[i].p = i - 1;
				kill(i - 1);
			}
			else {
				st2.push_back(node());
			}
 
			int o = i;
			if (t[i] <= T) {
				while (st.size() && st.back().ff >= t[i] - i) {
					st.pop_back();
				}
				st.push_back({ t[i] - i, i});
			}
			else {
				while (st.size() && st.back().ff > T - i) st.pop_back();
				if (st.size()) {
					o = st.back().ss;
				}
				else o = -1;
			}
			//cout << o << ",";
			if(o >= start){
				int t = pls.par(o);
				st2[t].lz++; amt++;
				kill(t);
			}
			//cout << amt << ",";
		}
		//cout << endl;
		int c = st2[start].c;
		//cout << c << endl;
		if (c <= D) {
			r = m;
			ans = round((double)st2[start].v + (double)amt - (double)D * m);
		}
		else {
			//cout << "fuck" << endl;
			l = m;
		}
	}
	cout << ans << endl;
	// n log n inverse ackermann n please pass i swear to god
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 476 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 824 ms 23940 KB Output is correct
3 Correct 775 ms 23944 KB Output is correct
4 Correct 773 ms 28772 KB Output is correct
5 Correct 699 ms 25920 KB Output is correct
6 Correct 567 ms 35132 KB Output is correct
7 Correct 866 ms 83132 KB Output is correct
8 Correct 562 ms 24804 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 476 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 6 ms 604 KB Output is correct
24 Correct 6 ms 652 KB Output is correct
25 Correct 6 ms 604 KB Output is correct
26 Correct 6 ms 648 KB Output is correct
27 Correct 6 ms 604 KB Output is correct
28 Correct 7 ms 572 KB Output is correct
29 Correct 6 ms 604 KB Output is correct
30 Correct 5 ms 664 KB Output is correct
31 Correct 5 ms 600 KB Output is correct
32 Correct 4 ms 604 KB Output is correct
33 Correct 4 ms 604 KB Output is correct
34 Correct 6 ms 604 KB Output is correct
35 Correct 5 ms 604 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 111 ms 3980 KB Output is correct
3 Correct 119 ms 3972 KB Output is correct
4 Correct 74 ms 3948 KB Output is correct
5 Correct 64 ms 7008 KB Output is correct
6 Correct 65 ms 6332 KB Output is correct
7 Correct 78 ms 6068 KB Output is correct
8 Correct 77 ms 7604 KB Output is correct
9 Correct 77 ms 12980 KB Output is correct
10 Correct 59 ms 4024 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 476 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 6 ms 604 KB Output is correct
24 Correct 6 ms 652 KB Output is correct
25 Correct 6 ms 604 KB Output is correct
26 Correct 6 ms 648 KB Output is correct
27 Correct 6 ms 604 KB Output is correct
28 Correct 7 ms 572 KB Output is correct
29 Correct 6 ms 604 KB Output is correct
30 Correct 5 ms 664 KB Output is correct
31 Correct 5 ms 600 KB Output is correct
32 Correct 4 ms 604 KB Output is correct
33 Correct 4 ms 604 KB Output is correct
34 Correct 6 ms 604 KB Output is correct
35 Correct 5 ms 604 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 111 ms 3980 KB Output is correct
38 Correct 119 ms 3972 KB Output is correct
39 Correct 74 ms 3948 KB Output is correct
40 Correct 64 ms 7008 KB Output is correct
41 Correct 65 ms 6332 KB Output is correct
42 Correct 78 ms 6068 KB Output is correct
43 Correct 77 ms 7604 KB Output is correct
44 Correct 77 ms 12980 KB Output is correct
45 Correct 59 ms 4024 KB Output is correct
46 Correct 1 ms 344 KB Output is correct
47 Correct 1 ms 348 KB Output is correct
48 Correct 1 ms 348 KB Output is correct
49 Correct 1 ms 348 KB Output is correct
50 Correct 1 ms 348 KB Output is correct
51 Correct 1 ms 348 KB Output is correct
52 Correct 1 ms 348 KB Output is correct
53 Correct 1 ms 348 KB Output is correct
54 Correct 1 ms 420 KB Output is correct
55 Correct 1 ms 348 KB Output is correct
56 Correct 1 ms 348 KB Output is correct
57 Correct 6 ms 648 KB Output is correct
58 Correct 6 ms 604 KB Output is correct
59 Correct 6 ms 604 KB Output is correct
60 Correct 6 ms 604 KB Output is correct
61 Correct 6 ms 652 KB Output is correct
62 Correct 6 ms 652 KB Output is correct
63 Correct 6 ms 604 KB Output is correct
64 Correct 4 ms 600 KB Output is correct
65 Correct 4 ms 604 KB Output is correct
66 Correct 3 ms 604 KB Output is correct
67 Correct 4 ms 604 KB Output is correct
68 Correct 5 ms 604 KB Output is correct
69 Correct 5 ms 792 KB Output is correct
70 Correct 1 ms 344 KB Output is correct
71 Correct 108 ms 3956 KB Output is correct
72 Correct 115 ms 3928 KB Output is correct
73 Correct 73 ms 3952 KB Output is correct
74 Correct 64 ms 7004 KB Output is correct
75 Correct 62 ms 6324 KB Output is correct
76 Correct 78 ms 6184 KB Output is correct
77 Correct 83 ms 7608 KB Output is correct
78 Correct 75 ms 13112 KB Output is correct
79 Correct 62 ms 4024 KB Output is correct
80 Correct 117 ms 3976 KB Output is correct
81 Correct 110 ms 3996 KB Output is correct
82 Correct 112 ms 3976 KB Output is correct
83 Correct 94 ms 5976 KB Output is correct
84 Correct 96 ms 3968 KB Output is correct
85 Correct 61 ms 5304 KB Output is correct
86 Correct 77 ms 5040 KB Output is correct
87 Correct 74 ms 4276 KB Output is correct
88 Correct 78 ms 12284 KB Output is correct
89 Correct 92 ms 12720 KB Output is correct
90 Correct 72 ms 10480 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 476 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 824 ms 23940 KB Output is correct
14 Correct 775 ms 23944 KB Output is correct
15 Correct 773 ms 28772 KB Output is correct
16 Correct 699 ms 25920 KB Output is correct
17 Correct 567 ms 35132 KB Output is correct
18 Correct 866 ms 83132 KB Output is correct
19 Correct 562 ms 24804 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 6 ms 604 KB Output is correct
32 Correct 6 ms 652 KB Output is correct
33 Correct 6 ms 604 KB Output is correct
34 Correct 6 ms 648 KB Output is correct
35 Correct 6 ms 604 KB Output is correct
36 Correct 7 ms 572 KB Output is correct
37 Correct 6 ms 604 KB Output is correct
38 Correct 5 ms 664 KB Output is correct
39 Correct 5 ms 600 KB Output is correct
40 Correct 4 ms 604 KB Output is correct
41 Correct 4 ms 604 KB Output is correct
42 Correct 6 ms 604 KB Output is correct
43 Correct 5 ms 604 KB Output is correct
44 Correct 1 ms 348 KB Output is correct
45 Correct 111 ms 3980 KB Output is correct
46 Correct 119 ms 3972 KB Output is correct
47 Correct 74 ms 3948 KB Output is correct
48 Correct 64 ms 7008 KB Output is correct
49 Correct 65 ms 6332 KB Output is correct
50 Correct 78 ms 6068 KB Output is correct
51 Correct 77 ms 7604 KB Output is correct
52 Correct 77 ms 12980 KB Output is correct
53 Correct 59 ms 4024 KB Output is correct
54 Correct 1 ms 344 KB Output is correct
55 Correct 1 ms 348 KB Output is correct
56 Correct 1 ms 348 KB Output is correct
57 Correct 1 ms 348 KB Output is correct
58 Correct 1 ms 348 KB Output is correct
59 Correct 1 ms 348 KB Output is correct
60 Correct 1 ms 348 KB Output is correct
61 Correct 1 ms 348 KB Output is correct
62 Correct 1 ms 420 KB Output is correct
63 Correct 1 ms 348 KB Output is correct
64 Correct 1 ms 348 KB Output is correct
65 Correct 6 ms 648 KB Output is correct
66 Correct 6 ms 604 KB Output is correct
67 Correct 6 ms 604 KB Output is correct
68 Correct 6 ms 604 KB Output is correct
69 Correct 6 ms 652 KB Output is correct
70 Correct 6 ms 652 KB Output is correct
71 Correct 6 ms 604 KB Output is correct
72 Correct 4 ms 600 KB Output is correct
73 Correct 4 ms 604 KB Output is correct
74 Correct 3 ms 604 KB Output is correct
75 Correct 4 ms 604 KB Output is correct
76 Correct 5 ms 604 KB Output is correct
77 Correct 5 ms 792 KB Output is correct
78 Correct 1 ms 344 KB Output is correct
79 Correct 108 ms 3956 KB Output is correct
80 Correct 115 ms 3928 KB Output is correct
81 Correct 73 ms 3952 KB Output is correct
82 Correct 64 ms 7004 KB Output is correct
83 Correct 62 ms 6324 KB Output is correct
84 Correct 78 ms 6184 KB Output is correct
85 Correct 83 ms 7608 KB Output is correct
86 Correct 75 ms 13112 KB Output is correct
87 Correct 62 ms 4024 KB Output is correct
88 Correct 117 ms 3976 KB Output is correct
89 Correct 110 ms 3996 KB Output is correct
90 Correct 112 ms 3976 KB Output is correct
91 Correct 94 ms 5976 KB Output is correct
92 Correct 96 ms 3968 KB Output is correct
93 Correct 61 ms 5304 KB Output is correct
94 Correct 77 ms 5040 KB Output is correct
95 Correct 74 ms 4276 KB Output is correct
96 Correct 78 ms 12284 KB Output is correct
97 Correct 92 ms 12720 KB Output is correct
98 Correct 72 ms 10480 KB Output is correct
99 Correct 1 ms 348 KB Output is correct
100 Correct 1 ms 348 KB Output is correct
101 Correct 1 ms 600 KB Output is correct
102 Correct 1 ms 348 KB Output is correct
103 Correct 1 ms 348 KB Output is correct
104 Correct 1 ms 348 KB Output is correct
105 Correct 1 ms 348 KB Output is correct
106 Correct 1 ms 348 KB Output is correct
107 Correct 1 ms 348 KB Output is correct
108 Correct 1 ms 348 KB Output is correct
109 Correct 1 ms 348 KB Output is correct
110 Correct 0 ms 348 KB Output is correct
111 Correct 782 ms 23972 KB Output is correct
112 Correct 760 ms 23944 KB Output is correct
113 Correct 733 ms 29028 KB Output is correct
114 Correct 683 ms 24132 KB Output is correct
115 Correct 563 ms 34936 KB Output is correct
116 Correct 889 ms 83316 KB Output is correct
117 Correct 570 ms 26728 KB Output is correct
118 Correct 6 ms 600 KB Output is correct
119 Correct 6 ms 600 KB Output is correct
120 Correct 7 ms 604 KB Output is correct
121 Correct 6 ms 604 KB Output is correct
122 Correct 6 ms 604 KB Output is correct
123 Correct 6 ms 604 KB Output is correct
124 Correct 6 ms 616 KB Output is correct
125 Correct 4 ms 604 KB Output is correct
126 Correct 4 ms 668 KB Output is correct
127 Correct 4 ms 604 KB Output is correct
128 Correct 4 ms 604 KB Output is correct
129 Correct 6 ms 604 KB Output is correct
130 Correct 5 ms 468 KB Output is correct
131 Correct 0 ms 348 KB Output is correct
132 Correct 120 ms 3988 KB Output is correct
133 Correct 116 ms 3932 KB Output is correct
134 Correct 75 ms 3952 KB Output is correct
135 Correct 63 ms 7000 KB Output is correct
136 Correct 63 ms 6324 KB Output is correct
137 Correct 79 ms 6180 KB Output is correct
138 Correct 78 ms 7604 KB Output is correct
139 Correct 76 ms 12980 KB Output is correct
140 Correct 63 ms 4020 KB Output is correct
141 Correct 114 ms 3928 KB Output is correct
142 Correct 105 ms 3932 KB Output is correct
143 Correct 122 ms 3928 KB Output is correct
144 Correct 94 ms 5976 KB Output is correct
145 Correct 95 ms 3928 KB Output is correct
146 Correct 62 ms 5304 KB Output is correct
147 Correct 77 ms 5040 KB Output is correct
148 Correct 71 ms 4280 KB Output is correct
149 Correct 75 ms 12208 KB Output is correct
150 Correct 76 ms 12712 KB Output is correct
151 Correct 67 ms 10608 KB Output is correct
152 Execution timed out 2017 ms 94424 KB Time limit exceeded
153 Halted 0 ms 0 KB -