Submission #591151

# Submission time Handle Problem Language Result Execution time Memory
591151 2022-07-06T23:11:43 Z GusterGoose27 The short shank; Redemption (BOI21_prison) C++11
45 / 100
2000 ms 63552 KB
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long double ld;
typedef pair<ld, int> pdi;
typedef pair<int, int> pii;
 
const int MAXN = 2e6;
const int MAX_ALLOC = (1 << 22);
pdi dp[MAXN];
const int inf = 1e9;
int m, d, t;
int vals[MAXN];
pdi mn[MAX_ALLOC];
int lz[MAX_ALLOC];
int lval[MAX_ALLOC];
int rval[MAX_ALLOC];
 
int n;
 
void make() {
	n = pow(2, ceil(log2(m)));
	for (int i = 1; i < 2*n; i++) mn[i] = pdi(inf, 0);
	for (int i = n; i < 2*n; i++) {
		lval[i] = i-n;
		rval[i] = i-n+1;
	}
	for (int i = n-1; i > 0; i--) {
		lval[i] = lval[2*i];
		rval[i] = rval[2*i+1];
	}
}
void clean() {
	for (int i = 1; i < 2*n; i++) mn[i] = pdi(inf, 0);
	fill(lz, lz+2*n, 0);
}
void increment(int l, int r, int v, int cur = 1) {
	if (lval[cur] >= r || rval[cur] <= l) return;
	if (lval[cur] >= l && rval[cur] <= r) {
		lz[cur] += v;
		mn[cur].first += v;
		return;
	}
	increment(l, r, v, 2*cur);
	increment(l, r, v, 2*cur+1);
	mn[cur] = min(mn[2*cur], mn[2*cur+1]);
	mn[cur].first += lz[cur];
}
pdi mnval(int l, int r, int cur = 1, int laz = 0) {
	if (lval[cur] >= r || rval[cur] <= l) return pdi(inf, 0);
	if (lval[cur] >= l && rval[cur] <= r) return pdi(mn[cur].first+laz, mn[cur].second);
	laz += lz[cur];
	return min(mnval(l, r, 2*cur, laz), mnval(l, r, 2*cur+1, laz));
}
void update(int i, pdi v, int cur = 1, int laz = 0) {
	if (lval[cur] > i || rval[cur] <= i) return;
	if (cur >= n) {
		mn[cur] = pdi(v.first-laz, v.second);
		return;
	}
	laz += lz[cur];
	update(i, v, 2*cur, laz);
	update(i, v, 2*cur+1, laz);
	mn[cur] = min(mn[2*cur], mn[2*cur+1]);
	mn[cur].first += lz[cur];
}
 
int iters = 25;
//const ld prec = 3e-2;
 
int get_int(int i) {
	if (vals[i] > t) return i;
	return i+(t-vals[i])+1;
}
 
bool make_iter(ld &mn, ld &mx, bool force = 0) {
	vector<int> uncolored;
	//STree s(n);
	ld cost = (mn+mx)/2;
	for (int i = m-1; i >= 0; i--) {
		if (i == m-1) dp[i] = pdi(0, 0);
		else {
			pdi mval = mnval(i+1, m);
			mval.first += cost;
			mval.second++;
			dp[i] = mval;
		}
		// if (dp[i].second > d) {
		// 	mn = cost;
		// 	return 0;
		// }
		if (d == 1 && dp[i].second > d) update(i, pdi(inf, 0));
		else update(i, dp[i]);
		uncolored.push_back(i);
		int r = get_int(i);
		int pos = uncolored.size()-1;
		while (pos >= 0 && uncolored[pos] < r) pos--;
		pos++;
		int prev = n;
		int mult = uncolored.size()-pos;
		for (int i = pos; i < uncolored.size(); i++) {
			increment(uncolored[i], prev, mult);
			prev = uncolored[i];
			mult--;
		}
		int num = uncolored.size()-pos;
		for (int i = 0; i < num; i++) uncolored.pop_back();
	}
	pdi overall = mnval(0, m-1);
	if (overall.second == d || force) { // we are done
		cout << round(overall.first-cost*d) << "\n";
		return 1;
	}
	if (overall.second < d) mx = cost;
	else mn = cost;
	return 0;
}
 
void spec() {
	vector<int> uncolored;
	//STree s(n);
	//ld cost = (mn+mx)/2;
	for (int i = m-1; i >= 0; i--) {
		if (i == m-1) dp[i] = pdi(0, 0);
		else {
			pdi mval = mnval(m-1, m);
			//mnval.first += cost;
			mval.second++;
			dp[i] = mval;
		}
		// if (dp[i].second > d) {
		// 	mn = cost;
		// 	return 0;
		// }
		if (d == 1 && dp[i].second > d) update(i, pdi(inf, 0));
		else update(i, dp[i]);
		uncolored.push_back(i);
		int r = get_int(i);
		int pos = uncolored.size()-1;
		while (pos >= 0 && uncolored[pos] < r) pos--;
		pos++;
		int prev = n;
		int mult = uncolored.size()-pos;
		for (int i = pos; i < uncolored.size(); i++) {
			increment(uncolored[i], prev, mult);
			prev = uncolored[i];
			mult--;
		}
		int num = uncolored.size()-pos;
		for (int i = 0; i < num; i++) uncolored.pop_back();
	}
	pdi overall = mnval(0, m-1);
	cout << round(overall.first) << "\n";
	return;
	// if (overall.second == d || force) { // we are done
	// 	cout << round(overall.first-cost*d) << "\n";
	// 	//return 1;
	// }
	// if (overall.second < d) mx = cost;
	// else mn = cost;
	// return 0;
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> m >> d >> t;
	//if (m > 75000) iters = 15;
	for (int i = 0; i < m; i++) cin >> vals[i];
	ld mn = 0;
	ld mx = ((ld)m)/d+1;
	make();
	if (d == 1) {
		spec();
		return 0;
	}
	for (int t = 0; t < iters; t++) {
	//while (mx-mn > prec) {
		bool fin = make_iter(mn, mx);
		if (fin) return 0;
		clean();
	}
	//assert(false);
	make_iter(mn, mx, 1);
}

Compilation message

prison.cpp: In function 'bool make_iter(ld&, ld&, bool)':
prison.cpp:105:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   for (int i = pos; i < uncolored.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~
prison.cpp: In function 'void spec()':
prison.cpp:148:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |   for (int i = pos; i < uncolored.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 8 ms 340 KB Output is correct
3 Correct 7 ms 416 KB Output is correct
4 Correct 8 ms 340 KB Output is correct
5 Correct 8 ms 424 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 8 ms 340 KB Output is correct
9 Correct 8 ms 340 KB Output is correct
10 Correct 7 ms 340 KB Output is correct
11 Correct 7 ms 432 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 565 ms 62884 KB Output is correct
3 Correct 550 ms 62944 KB Output is correct
4 Correct 532 ms 63112 KB Output is correct
5 Correct 532 ms 62992 KB Output is correct
6 Correct 469 ms 62792 KB Output is correct
7 Correct 490 ms 63408 KB Output is correct
8 Correct 503 ms 63552 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 8 ms 340 KB Output is correct
3 Correct 7 ms 416 KB Output is correct
4 Correct 8 ms 340 KB Output is correct
5 Correct 8 ms 424 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 8 ms 340 KB Output is correct
9 Correct 8 ms 340 KB Output is correct
10 Correct 7 ms 340 KB Output is correct
11 Correct 7 ms 432 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 7 ms 424 KB Output is correct
14 Correct 9 ms 420 KB Output is correct
15 Correct 8 ms 340 KB Output is correct
16 Correct 9 ms 340 KB Output is correct
17 Correct 3 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 8 ms 340 KB Output is correct
20 Correct 8 ms 340 KB Output is correct
21 Correct 8 ms 432 KB Output is correct
22 Correct 7 ms 340 KB Output is correct
23 Correct 79 ms 852 KB Output is correct
24 Correct 79 ms 860 KB Output is correct
25 Correct 94 ms 852 KB Output is correct
26 Correct 79 ms 852 KB Output is correct
27 Correct 77 ms 852 KB Output is correct
28 Correct 81 ms 852 KB Output is correct
29 Correct 87 ms 852 KB Output is correct
30 Correct 71 ms 856 KB Output is correct
31 Correct 71 ms 852 KB Output is correct
32 Correct 70 ms 852 KB Output is correct
33 Correct 71 ms 856 KB Output is correct
34 Correct 13 ms 872 KB Output is correct
35 Correct 78 ms 860 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 2089 ms 14228 KB Time limit exceeded
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 8 ms 340 KB Output is correct
3 Correct 7 ms 416 KB Output is correct
4 Correct 8 ms 340 KB Output is correct
5 Correct 8 ms 424 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 8 ms 340 KB Output is correct
9 Correct 8 ms 340 KB Output is correct
10 Correct 7 ms 340 KB Output is correct
11 Correct 7 ms 432 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 7 ms 424 KB Output is correct
14 Correct 9 ms 420 KB Output is correct
15 Correct 8 ms 340 KB Output is correct
16 Correct 9 ms 340 KB Output is correct
17 Correct 3 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 8 ms 340 KB Output is correct
20 Correct 8 ms 340 KB Output is correct
21 Correct 8 ms 432 KB Output is correct
22 Correct 7 ms 340 KB Output is correct
23 Correct 79 ms 852 KB Output is correct
24 Correct 79 ms 860 KB Output is correct
25 Correct 94 ms 852 KB Output is correct
26 Correct 79 ms 852 KB Output is correct
27 Correct 77 ms 852 KB Output is correct
28 Correct 81 ms 852 KB Output is correct
29 Correct 87 ms 852 KB Output is correct
30 Correct 71 ms 856 KB Output is correct
31 Correct 71 ms 852 KB Output is correct
32 Correct 70 ms 852 KB Output is correct
33 Correct 71 ms 856 KB Output is correct
34 Correct 13 ms 872 KB Output is correct
35 Correct 78 ms 860 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Execution timed out 2089 ms 14228 KB Time limit exceeded
38 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 8 ms 340 KB Output is correct
3 Correct 7 ms 416 KB Output is correct
4 Correct 8 ms 340 KB Output is correct
5 Correct 8 ms 424 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 8 ms 340 KB Output is correct
9 Correct 8 ms 340 KB Output is correct
10 Correct 7 ms 340 KB Output is correct
11 Correct 7 ms 432 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 565 ms 62884 KB Output is correct
14 Correct 550 ms 62944 KB Output is correct
15 Correct 532 ms 63112 KB Output is correct
16 Correct 532 ms 62992 KB Output is correct
17 Correct 469 ms 62792 KB Output is correct
18 Correct 490 ms 63408 KB Output is correct
19 Correct 503 ms 63552 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 7 ms 424 KB Output is correct
22 Correct 9 ms 420 KB Output is correct
23 Correct 8 ms 340 KB Output is correct
24 Correct 9 ms 340 KB Output is correct
25 Correct 3 ms 340 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Correct 8 ms 340 KB Output is correct
28 Correct 8 ms 340 KB Output is correct
29 Correct 8 ms 432 KB Output is correct
30 Correct 7 ms 340 KB Output is correct
31 Correct 79 ms 852 KB Output is correct
32 Correct 79 ms 860 KB Output is correct
33 Correct 94 ms 852 KB Output is correct
34 Correct 79 ms 852 KB Output is correct
35 Correct 77 ms 852 KB Output is correct
36 Correct 81 ms 852 KB Output is correct
37 Correct 87 ms 852 KB Output is correct
38 Correct 71 ms 856 KB Output is correct
39 Correct 71 ms 852 KB Output is correct
40 Correct 70 ms 852 KB Output is correct
41 Correct 71 ms 856 KB Output is correct
42 Correct 13 ms 872 KB Output is correct
43 Correct 78 ms 860 KB Output is correct
44 Correct 0 ms 340 KB Output is correct
45 Execution timed out 2089 ms 14228 KB Time limit exceeded
46 Halted 0 ms 0 KB -