oj.uz

Submission #852374

# Submission time Handle Problem Language Result Execution time Memory
852374 2023-09-21T16:38:12 Z adaawf Holiday (IOI14_holiday) C++14
100 / 100
 266 ms 15300 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include "holiday.h"
using namespace std;
pair<int, int> a[400005];
long long f[400005], g[400005], res = 0;
int d;
struct DAY {
	long long int res, c;
};
DAY t[1600005];
void update(int v, int x) {
 	v += 400005;
	if (x < 0) t[v].c = 0;
	else t[v].c = 1;
	t[v].res += x;
	v /= 2;
	while (v > 0) {
		t[v].c = t[v * 2].c + t[v * 2 + 1].c;
		t[v].res = t[v * 2].res + t[v * 2 + 1].res;
		v /= 2;
	}
}
long long int sum(int v, int l, int r, int x) {
	if (t[v].c == 0 || x <= 0) return 0;
	if (t[v].c <= x) return t[v].res;
    int mid = (l + r) / 2;
    if (t[v * 2 + 1].c >= x) return sum(v * 2 + 1, mid + 1, r, x);
    return t[v * 2 + 1].res + sum(v * 2, l, mid, x - t[v * 2 + 1].c);
}
int ll = 0, rr = -1;
void trya(int x, int y) {
	while (ll > x) {
		ll--;
		update(a[ll].second, a[ll].first);
	}
	while (rr < y) {
		rr++;
		update(a[rr].second, a[rr].first);
	}
	while (ll < x) {
		update(a[ll].second, -a[ll].first);
		ll++;
	}
	while (rr > y) {
		update(a[rr].second, -a[rr].first);
		rr--;
	}
}
void dnc(int l, int r, int x, int y, int k) {
    if (l > r) return;
	int mid = (l + r) / 2;
	trya(x, mid);
	int h = x;
	for (int i = x; i <= min(mid, y) && i <= k; i++) {
		int c = (k - i) + (mid - i);
		if (d - c > 0) {
			long long int k = sum(1, 0, 400004, d - c);
			if (f[mid] <= k) {
				f[mid] = k;
				res = max(res, k);
				h = i;
			}
		}
		update(a[i].second, -a[i].first);
		ll++;
	}
	dnc(l, mid - 1, x, h, k);
	dnc(mid + 1, r, h, y, k);
}
void dnc2(int l, int r, int x, int y, int k) {
    if (l > r) return;
	int mid = (l + r) / 2;
	trya(mid, y);
	int h = y;
	for (int i = y; i >= max(mid, x) && i >= k; i--) {
		int c = (i - k) + (i - mid);
		if (d - c > 0) {
			long long int k = sum(1, 0, 400004, d - c);
			if (g[mid] <= k) {
				g[mid] = k;
				res = max(res, k);
				h = i;
			}
		}
		update(a[i].second, -a[i].first);
		rr--;
	}
	dnc2(l, mid - 1, x, h, k);
	dnc2(mid + 1, r, h, y, k);
}
long long int findMaxAttraction(int n, int k, int dd, int attraction[]) {
	vector<pair<int, int>> v;
	for (int i = 0; i < n; i++) {
		v.push_back({attraction[i], i});
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < n; i++) {
		a[v[i].second] = {v[i].first, i};
	}
	d = dd;
	dnc(k, n - 1, 0, n - 1, k);
	dnc2(0, k, 0, n - 1, k);
    return res;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB Output is correct
2 Correct 2 ms 11096 KB Output is correct
3 Correct 3 ms 11096 KB Output is correct
4 Correct 2 ms 11352 KB Output is correct
5 Correct 2 ms 11096 KB Output is correct
6 Correct 3 ms 11100 KB Output is correct
7 Correct 2 ms 11096 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 14784 KB Output is correct
2 Correct 65 ms 14792 KB Output is correct
3 Correct 61 ms 14796 KB Output is correct
4 Correct 62 ms 14796 KB Output is correct
5 Correct 75 ms 14612 KB Output is correct
6 Correct 19 ms 13772 KB Output is correct
7 Correct 36 ms 14036 KB Output is correct
8 Correct 44 ms 14280 KB Output is correct
9 Correct 14 ms 13524 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11096 KB Output is correct
2 Correct 3 ms 11100 KB Output is correct
3 Correct 3 ms 11096 KB Output is correct
4 Correct 6 ms 11096 KB Output is correct
5 Correct 6 ms 11096 KB Output is correct
6 Correct 3 ms 11096 KB Output is correct
7 Correct 3 ms 11096 KB Output is correct
8 Correct 3 ms 11252 KB Output is correct
9 Correct 3 ms 11096 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 14028 KB Output is correct
2 Correct 61 ms 14788 KB Output is correct
3 Correct 88 ms 13520 KB Output is correct
4 Correct 6 ms 11164 KB Output is correct
5 Correct 3 ms 11096 KB Output is correct
6 Correct 3 ms 11096 KB Output is correct
7 Correct 3 ms 11096 KB Output is correct
8 Correct 266 ms 15300 KB Output is correct
9 Correct 265 ms 15300 KB Output is correct