oj.uz

Submission #58661

# Submission time Handle Problem Language Result Execution time Memory
58661 2018-07-18T16:57:04 Z aome Holiday (IOI14_holiday) C++17
100 / 100
 622 ms 56144 KB 
#include "holiday.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

int n, d, start;
int a[N];
int ver[N];

struct SegmentTree {
	struct Node {
		int l, r;
		int cnt;
		long long sum;
		
		Node() { cnt = sum = 0; }
	};

	int num;
	Node T[N * 20];

	#define mid ((l + r) >> 1)

	void build(int i, int l, int r) {
		if (l == r) return;
		T[i].l = ++num;
		build(T[i].l, l, mid);
		T[i].r = ++num;
		build(T[i].r, mid + 1, r);
	}

	void upd(int i, int j, int l, int r, int p, int x) {
		T[i].cnt = T[j].cnt + 1, T[i].sum = T[j].sum + x;
		if (l == r) return;
		if (mid >= p) {
			T[i].l = ++num, T[i].r = T[j].r;
			upd(T[i].l, T[j].l, l, mid, p, x);
		}
		else {
			T[i].l = T[j].l, T[i].r = ++num;
			upd(T[i].r, T[j].r, mid + 1, r, p, x);
		}
	}

	long long get(int i, int j, int k) {
		int cnt;
		long long sum;
		long long ret = 0;
		while (k) {
			cnt = T[i].cnt - T[j].cnt;
			sum = T[i].sum - T[j].sum;
			if (k == cnt) {
				k -= cnt, ret += sum; break;
			}
			cnt = T[T[i].r].cnt - T[T[j].r].cnt;
			sum = T[T[i].r].sum - T[T[j].r].sum;
			if (k >= cnt) {
				k -= cnt, ret += sum;
				i = T[i].l, j = T[j].l; 
			}
			else {
				i = T[i].r, j = T[j].r;
			}
		}
		return ret;
	}

	#undef mid

} IT;

long long res;

void go(int l, int r, int L, int R) {
	if (l > r) return;
	int mid = (l + r) >> 1;
	int pos = 0;
	long long opt = 0;
	for (int i = L; i <= R; ++i) {
		int tmp = d - (mid - start) - (mid - i);
		tmp = max(tmp, 0);
		tmp = min(tmp, (mid - i + 1));
		long long val = IT.get(ver[mid], ver[i - 1], tmp);
		if (val >= opt) opt = val, pos = i;
	}
	res = max(res, opt);
	go(l, mid - 1, L, pos);
	go(mid + 1, r, pos, R);
}

void solve() {
	IT.num = 0, IT.build(0, 1, n);
	vector< pair<int, int> > vec;
	for (int i = 1; i <= n; ++i) vec.push_back({a[i], i});
	sort(vec.begin(), vec.end());
	int cur = 0;
	for (int i = 1; i <= n; ++i) {
		int tmp = lower_bound(vec.begin(), vec.end(), make_pair(a[i], i)) - vec.begin() + 1;
		ver[i] = ++IT.num;
		IT.upd(ver[i], ver[i - 1], 1, n, tmp, a[i]);
	}
	go(start, n, 1, start);
}

long long int findMaxAttraction(int _n, int _start, int _d, int attraction[]) {
	n = _n, d = _d, start = _start + 1;
	for (int i = 1; i <= n; ++i) a[i] = attraction[i - 1];
	solve();
	reverse(a + 1, a + n + 1);
	start = n + 1 - start;
	solve();
	return res;
}

Compilation message

holiday.cpp: In function 'void solve()':
holiday.cpp:99:6: warning: unused variable 'cur' [-Wunused-variable]
  int cur = 0;
      ^~~
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 47224 KB Output is correct
2 Correct 35 ms 47336 KB Output is correct
3 Correct 41 ms 47416 KB Output is correct
4 Correct 45 ms 47456 KB Output is correct
5 Correct 39 ms 47456 KB Output is correct
6 Correct 43 ms 47592 KB Output is correct
7 Correct 41 ms 47592 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 50628 KB Output is correct
2 Correct 143 ms 50928 KB Output is correct
3 Correct 167 ms 51020 KB Output is correct
4 Correct 140 ms 51344 KB Output is correct
5 Correct 237 ms 51396 KB Output is correct
6 Correct 72 ms 51396 KB Output is correct
7 Correct 118 ms 51396 KB Output is correct
8 Correct 136 ms 51396 KB Output is correct
9 Correct 63 ms 51396 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 51396 KB Output is correct
2 Correct 46 ms 51396 KB Output is correct
3 Correct 37 ms 51396 KB Output is correct
4 Correct 41 ms 51396 KB Output is correct
5 Correct 46 ms 51396 KB Output is correct
6 Correct 39 ms 51396 KB Output is correct
7 Correct 36 ms 51396 KB Output is correct
8 Correct 38 ms 51396 KB Output is correct
9 Correct 37 ms 51396 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 53096 KB Output is correct
2 Correct 127 ms 54036 KB Output is correct
3 Correct 202 ms 54036 KB Output is correct
4 Correct 47 ms 54036 KB Output is correct
5 Correct 41 ms 54036 KB Output is correct
6 Correct 43 ms 54036 KB Output is correct
7 Correct 36 ms 54036 KB Output is correct
8 Correct 622 ms 55364 KB Output is correct
9 Correct 577 ms 56144 KB Output is correct