oj.uz

Submission #499418

# Submission time Handle Problem Language Result Execution time Memory
499418 2021-12-28T11:30:53 Z pavement Holiday (IOI14_holiday) C++17
100 / 100
 382 ms 3924 KB 
#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int L, R, n, start, d, a[100005], rev[100005], disc[100005];
ll ans;
pair<ll, int> ft[100005];
vector<int> disc_v;
 
inline int ls(int x) { return x & -x; }
 
void add(int x) {
	for (int y = disc[x]; y <= disc_v.size(); y += ls(y))
		ft[y].first += a[x], ft[y].second++;
}
 
void del(int x) {
	for (int y = disc[x]; y <= disc_v.size(); y += ls(y))
		ft[y].first -= a[x], ft[y].second--;
}
 
pair<ll, int> qry(int x) {
	pair<ll, int> ret = make_pair(0ll, 0);
	for (; x; x -= ls(x))
		ret.first += ft[x].first, ret.second += ft[x].second;
	return ret;
}
 
ll cost(int k) { // sum of largest k things inside container
	if (k <= 0) return 0;
	if (k >= qry(disc_v.size()).second) return qry(disc_v.size()).first;
	int curr = 0, rs = 0;
	for (int i = 17; i >= 0; i--)
		if (curr + (1 << i) <= disc_v.size() && ft[curr + (1 << i)].second + rs < k) {
			rs += ft[curr + (1 << i)].second;
			curr += (1 << i);
		}
	return qry(curr).first + (ll)(k - rs) * rev[curr + 1];
}
 
void shift(int l, int r) {
	while (l < L) add(--L);
	while (r > R) add(++R);
	while (l > L) del(L++);
	while (r < R) del(R--);
}
 
void dnc(int l, int r, int x, int y) {
	if (l > r) return;
	int m = (l + r) >> 1, opt = -1;
	ll curr = -1, tmp;
	for (int i = y; i >= x; i--) {
		shift(i, m);
		tmp = cost(d - 2 * (m - start) - (start - i));
		if (tmp > curr) {
			curr = tmp;
			opt = i;
		}
	}
	assert(opt != -1);
	ans = max(ans, curr);
	dnc(l, m - 1, x, opt);
	dnc(m + 1, r, opt, y);
}
 
ll findMaxAttraction(int _n, int _start, int _d, int _attraction[]) {
	n = _n;
	start = _start;
	d = _d;
	for (int i = 0; i < n; i++) {
		a[i] = _attraction[i];
		disc_v.push_back(a[i]);
	}
	sort(disc_v.begin(), disc_v.end());
	disc_v.erase(unique(disc_v.begin(), disc_v.end()), disc_v.end());
	for (int i = 0; i < n; i++) {
		disc[i] = disc_v.size() - (lower_bound(disc_v.begin(), disc_v.end(), a[i]) - disc_v.begin() + 1) + 1;
		rev[disc[i]] = a[i];
	}
	L = R = start;
	add(start);
	for (int i = start; i < n; i++) {
		shift(start, i);
		ans = max(ans, cost(d - (i - start)));
	}
	for (int i = start - 1; i >= 0; i--) {
		shift(i, start);
		ans = max(ans, cost(d - (start - i)));
	}
	dnc(start, n - 1, 0, start);
	
	_start = _n - _start - 1;
	reverse(_attraction, _attraction + _n);
	
	memset(a, 0, sizeof a);
	memset(rev, 0, sizeof rev);
	memset(disc, 0, sizeof disc);
	for (int i = 1; i <= n; i++) ft[i] = make_pair(0ll, 0);
	disc_v.clear();
	
	n = _n;
	start = _start;
	d = _d;
	for (int i = 0; i < n; i++) {
		a[i] = _attraction[i];
		disc_v.push_back(a[i]);
	}
	sort(disc_v.begin(), disc_v.end());
	disc_v.erase(unique(disc_v.begin(), disc_v.end()), disc_v.end());
	for (int i = 0; i < n; i++) {
		disc[i] = disc_v.size() - (lower_bound(disc_v.begin(), disc_v.end(), a[i]) - disc_v.begin() + 1) + 1;
		rev[disc[i]] = a[i];
	}
	L = R = start;
	add(start);
	dnc(start, n - 1, 0, start);
	return ans;
}

Compilation message

holiday.cpp: In function 'void add(int)':
holiday.cpp:15:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  for (int y = disc[x]; y <= disc_v.size(); y += ls(y))
      |                        ~~^~~~~~~~~~~~~~~~
holiday.cpp: In function 'void del(int)':
holiday.cpp:20:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for (int y = disc[x]; y <= disc_v.size(); y += ls(y))
      |                        ~~^~~~~~~~~~~~~~~~
holiday.cpp: In function 'll cost(int)':
holiday.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   if (curr + (1 << i) <= disc_v.size() && ft[curr + (1 << i)].second + rs < k) {
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 1 ms 1840 KB Output is correct
3 Correct 1 ms 1836 KB Output is correct
4 Correct 1 ms 1868 KB Output is correct
5 Correct 2 ms 1868 KB Output is correct
6 Correct 1 ms 1740 KB Output is correct
7 Correct 2 ms 1840 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3916 KB Output is correct
2 Correct 22 ms 3924 KB Output is correct
3 Correct 23 ms 3924 KB Output is correct
4 Correct 22 ms 3904 KB Output is correct
5 Correct 47 ms 3704 KB Output is correct
6 Correct 14 ms 2508 KB Output is correct
7 Correct 26 ms 2888 KB Output is correct
8 Correct 38 ms 3136 KB Output is correct
9 Correct 13 ms 2380 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3852 KB Output is correct
2 Correct 59 ms 3860 KB Output is correct
3 Correct 101 ms 2752 KB Output is correct
4 Correct 5 ms 1868 KB Output is correct
5 Correct 2 ms 1868 KB Output is correct
6 Correct 2 ms 1868 KB Output is correct
7 Correct 3 ms 1868 KB Output is correct
8 Correct 366 ms 3832 KB Output is correct
9 Correct 382 ms 3896 KB Output is correct