Submission #603701

#	Time	Username	Problem	Language	Result	Execution time	Memory
603701		8e7	Holiday (IOI14_holiday)	C++17	100 / 100	1859 ms	14952 KiB

holiday

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
	while (l != r)cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<ll, ll>
#define ff first
#define ss second
#include"holiday.h"

ll p[maxn];
struct segtree{
	ll seg[4*maxn], cnt[4*maxn];
	void modify(int cur, int l, int r, int ind) {
		if (r <= l) return;
		if (r - l == 1) {
			if (cnt[cur]) {
				cnt[cur] = 0;
				seg[cur] = 0;	
			} else {
				cnt[cur] = 1;
				seg[cur] = p[l];
			}
			return;
		}
		int m = (l + r) / 2;
		if (ind < m) modify(cur*2, l, m, ind);
		else modify(cur*2+1, m, r, ind);
		seg[cur] = seg[cur*2] + seg[cur*2+1];
		cnt[cur] = cnt[cur*2] + cnt[cur*2+1];
	}
	ll getval(int cur, int l, int r, int k) {
		if (r <= l || k <= 0) return 0;
		if (cnt[cur] <= k) return seg[cur];
		int m = (l + r) / 2;	
		if (cnt[cur*2+1] >= k) return getval(cur*2+1, m, r, k);
		else return seg[cur*2+1] + getval(cur*2, l, m, k - cnt[cur*2+1]);
	}
} tr;
int n;
void solve(int l, int r, int ql, int qr, vector<int> &a, int stop, vector<ll> &ret) {
	if (r <= l || a.size() == 0) return;
	int m = (l + r) / 2; //solving for f(m)
	//[0, ql) has been inserted into tree
	ll best = -1;
	int bind = ql;
	for (int i = ql;i < qr;i++) {
		tr.modify(1, 0, n, a[i]);
		ll val = tr.getval(1, 0, n, m - i * stop);
		if (val > best) {
			best = val;
			bind = i;
		}
	}
	for (int i = ql;i < qr;i++) tr.modify(1, 0, n, a[i]);
	ret[m] = best;
	solve(l, m, ql, bind+1, a, stop, ret);
	for (int i = ql;i < bind;i++) tr.modify(1, 0, n, a[i]);
	solve(m+1, r, bind, qr, a, stop, ret);	
	for (int i = ql;i < bind;i++) tr.modify(1, 0, n, a[i]);	
}
long long int findMaxAttraction(int N, int st, int d, int H[]) {
	if (d == 0) return 0;
	n = N;
	vector<pii> v(n);	
	vector<int> idx(n);
	for (int i = 0;i < n;i++) v[i] = {H[i], i};
	sort(v.begin(), v.end());
	for (int i = 0;i < n;i++) p[i] = v[i].ff, idx[v[i].ss] = i;
	vector<int> a;
	for (int i = st;i < n;i++) a.push_back(idx[i]);
	vector<ll> l1(2*n+1), l2(2*n+1);		
	vector<ll> r1(2*n+1), r2(2*n+1);		
	solve(0, 2*n+1, 0, a.size(), a, 1, l1);
	solve(0, 2*n+1, 0, a.size(), a, 2, l2);
	a.clear();	
	for (int i = st-1;i >= 0;i--) a.push_back(idx[i]);
	solve(0, 2*n+1, 0, a.size(), a, 1, r1);
	solve(0, 2*n+1, 0, a.size(), a, 2, r2);
	/*
	pary(l1.begin(), l1.end());
	pary(l2.begin(), l2.end());
	pary(r1.begin(), r1.end());
	pary(r2.begin(), r2.end());
	*/
	ll ans = 0;
	if (d < l1.size()) ans = max(ans, l1[d]);
	else ans = max(ans, l1.back());
	if (d-1 < r1.size()) ans = max(ans, r1[d-1]);
	else ans = max(ans, r1.back());

	for (int i = 0;i < l1.size();i++) {
		if (d - i - 2 >= 0) {
			ans = max(ans, l1[i] + (d - i - 2 >= r2.size() ? r2.back() : r2[d - i - 2]));	
		}
	}
	for (int i = 0;i < r1.size();i++) {
		if (d - i - 1 >= 0) {
			ans = max(ans, r1[i] + (d - i-1 >= l2.size() ? l2.back() : l2[d - i-1]));	
		}
	}
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:98:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |  if (d < l1.size()) ans = max(ans, l1[d]);
      |      ~~^~~~~~~~~~~
holiday.cpp:100:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  if (d-1 < r1.size()) ans = max(ans, r1[d-1]);
      |      ~~~~^~~~~~~~~~~
holiday.cpp:103:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |  for (int i = 0;i < l1.size();i++) {
      |                 ~~^~~~~~~~~~~
holiday.cpp:105:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |    ans = max(ans, l1[i] + (d - i - 2 >= r2.size() ? r2.back() : r2[d - i - 2]));
      |                            ~~~~~~~~~~^~~~~~~~~~~~
holiday.cpp:108:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |  for (int i = 0;i < r1.size();i++) {
      |                 ~~^~~~~~~~~~~
holiday.cpp:110:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |    ans = max(ans, r1[i] + (d - i-1 >= l2.size() ? l2.back() : l2[d - i-1]));
      |                            ~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53