Submission #586832

#	Time	Username	Problem	Language	Result	Execution time	Memory
586832		Red_Inside	Holiday (IOI14_holiday)	C++17	100 / 100	456 ms	8028 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define forn(j, i, n) for(int i = j; i <= n; ++i)
#define FOR(j, i, n) for(int i = j; i < n; ++i)
#define nfor(j, i, n) for(int i = n; i >= j; --i)
#define IOS ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
#define all(v) v.begin(), v.end()

const int maxn = 1e5+100;

//#define int ll
#define pii pair <int, int>
ll inf = 1e18;

ll n, m, ukl, ukr, d, ts[4*maxn], tc[4*maxn], pos[maxn], a[maxn], res = -inf;
pair <ll, int> b[maxn];

void upd(int v, int tl, int tr, int pos, ll val)
{
//	if(v == 1) cout << "UPDATE " << pos << " " << val << endl;
	if(pos < tl || tr < pos) return;
	if(tl == tr)
	{
		ts[v] += val;
		if(ts[v] > 0) tc[v]++;
		else tc[v]--;
		return;
	}
	upd(v * 2, tl, (tl + tr) / 2, pos, val);
	upd(v * 2 + 1, (tl + tr) / 2 + 1, tr, pos, val);
	ts[v] = ts[v * 2] + ts[v * 2 + 1];
	tc[v] = tc[v * 2] + tc[v * 2 + 1];
}

ll get(int v, int tl, int tr, int k)
{
	if(tl == tr)
	{
		return ts[v];
	}
	if(tc[v * 2 + 1] >= k) return get(v * 2 + 1, (tl + tr) / 2 + 1, tr, k);
	else return get(v * 2, tl, (tl + tr) / 2, k - tc[v * 2 + 1]) + ts[v * 2 + 1];
}

void print(int v, int tl, int tr)
{
	if(tl == tr)
	{
		cout << tl << " " << tr << " " << ts[v] << " " << tc[v] << endl;
		return;
	}
	print(v * 2, tl, (tl + tr) / 2);
	cout << tl << " " << tr << " " << ts[v] << " " << tc[v] << endl;
	print(v * 2 + 1, (tl + tr) / 2 + 1, tr);
}

void solve(int l, int r, int optl = m, int optr = n)
{
	if(l > r) return;
	int mid = (l + r) / 2;
	while(ukl > mid)
	{
		ukl--;
		upd(1, 1, n, pos[ukl], a[ukl]);
	}
	while(ukl < mid)
	{
		upd(1, 1, n, pos[ukl], -a[ukl]);
		ukl++;
	}
	ll ans = -inf;
	int opt;
	forn(optl, i, optr)
	{
		while(ukr < i)
		{
			ukr++;
			upd(1, 1, n, pos[ukr], a[ukr]);
		}
		while(ukr > i)
		{
			upd(1, 1, n, pos[ukr], -a[ukr]);
			ukr--;
		}
		//m-mid
		//i-m
//		cout << "FOR " << mid << " " << i << " " << d-(i-mid+min(i-m, m-mid)) << " " << get(1, 1, n, d-(i-mid+min(i-m, m-mid))) << " " << ukl << " " << ukr << endl;
//		print(1, 1, n);
		ll temp = get(1, 1, n, d-(i-mid+min(i-m, m-mid)));
		res = max(res, temp);
		if(temp > ans)
		{
			ans = temp;
			opt = i;
		}
	}
//	cout << mid << " " << opt << endl;
	solve(l, mid-1, optl, opt);
	solve(mid+1, r, opt, optr);
}

long long int findMaxAttraction(int N, int start, int D, int attraction[]) 
{
	n = N;
	d = D;
	forn(1, i, n)
	{
		b[i].f = attraction[i-1];
		b[i].s = i;
		a[i] = b[i].f;
	}
	sort(b + 1, b + 1 + n);
	forn(1, i, n)
	{
		pos[b[i].s] = i;
	}
	start++;
	m = start;
	ukr = start;
	ukl = start;
	upd(1, 1, n, pos[start], a[start]);
	solve(1, start);
	return res;
}

Compilation message (stderr)

holiday.cpp: In function 'void solve(int, int, int, int)':
holiday.cpp:102:7: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |  solve(l, mid-1, optl, opt);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~

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