Submission #473107

#	Time	Username	Problem	Language	Result	Execution time	Memory
473107		jwvg0425	Holiday (IOI14_holiday)	C++17	100 / 100	782 ms	53616 KiB

holiday

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using Pt = pair<i64, int>;

struct Node
{
	int lidx, ridx;
	Pt value;

	Node() :value(Pt()), lidx(-1), ridx(-1) {}
};

Node node[2000005];

class PST
{

public:
	class iterator
	{
	public:
		iterator(PST& p, int n)
			: pst(p), nx(n) {}

		iterator& operator=(const iterator& other)
		{
			nx = other.nx;
			return *this;
		}

		Pt get() const
		{
			return node[nx].value;
		}

		iterator left() const
		{
			return iterator(pst, node[nx].lidx);
		}

		iterator right() const
		{
			return iterator(pst, node[nx].ridx);
		}

	private:
		PST& pst;
		int nx;
	};

	template<typename M>
	PST(int n_, const M& m) : n(n_), merge(m)
	{
	}

	iterator it(int r)
	{
		return iterator(*this, root[r]);
	}

	int rmost() const
	{
		return n;
	}

	int update(int idx, const Pt& value)
	{
		return update((int)root.size() - 1, idx, value);
	}

	int update(int pre, int idx, const Pt& value)
	{
		root.emplace_back(_update(root[pre], idx, value, 0, n));
		return (int)root.size() - 1;
	}

	Pt query(int k, int start, int end)
	{
		return _query(root[k], start, end, 0, n);
	}

	void init()
	{
		root.push_back(init(0, n));
	}

private:
	int init(int start, int end)
	{
		int idx = sz;
		sz++;

		if (start != end)
		{
			int mid = (start + end) / 2;

			node[idx].lidx = init(start, mid);
			node[idx].ridx = init(mid + 1, end);
		}
		return idx;
	}

	int _update(int prev, int idx, const Pt& value, int start, int end)
	{
		if (idx < start || idx > end)
			return prev;

		int nidx = sz;
		sz++;

		if (start == end)
			node[nidx].value = value;
		else
		{
			int mid = (start + end) / 2;
			node[nidx].lidx = _update(node[prev].lidx, idx, value, start, mid);
			node[nidx].ridx = _update(node[prev].ridx, idx, value, mid + 1, end);
			node[nidx].value = merge(node[node[nidx].lidx].value, node[node[nidx].ridx].value);
		}

		return nidx;
	}

	Pt _query(int idx, int start, int end, int left, int right)
	{
		if (start <= left && right <= end)
			return node[idx].value;

		int mid = (left + right) / 2;

		if (mid + 1 > end)
			return _query(node[idx].lidx, start, end, left, mid);

		if (mid < start)
			return _query(node[idx].ridx, start, end, mid + 1, right);

		return merge(_query(node[idx].lidx, start, end, left, mid),
			_query(node[idx].ridx, start, end, mid + 1, right));
	}

	using Merge = function<Pt(const Pt&, const Pt&)>;
	Merge merge;
	vector<int> root;
	int n;
	int sz = 0;
};

int n, s, d;
auto tree = PST(100005, [](const Pt& l, const Pt& r) { return Pt(l.xx + r.xx, l.yy + r.yy); });
vector<i64> arr;

i64 get(int l, int r)
{
	int cnt = min(r - l + 1, d + 2 * l - r - s);

	if (cnt <= 0)
		return 0;

	i64 res = 0;
	auto lx = tree.it(l - 1);
	auto rx = tree.it(r);

	int s = 0, e = 100005;
	int need = cnt;

	while (need > 0)
	{
		if (s == e)
		{
			res += rx.get().xx - lx.get().xx;
			break;
		}

		int m = (s + e) / 2;
		auto lr = lx.right();
		auto rr = rx.right();

		if (rr.get().yy - lr.get().yy >= need)
		{
			lx = lr;
			rx = rr;
			s = m + 1;
			continue;
		}

		need -= rr.get().yy - lr.get().yy;
		res += rr.get().xx - lr.get().xx;
		lx = lx.left();
		rx = rx.left();
		e = m;
	}

	return res;
}

i64 big[100005];

void f(int y1, int y2, int x1, int x2)
{
	if (y1 > y2 || x1 > x2)
		return;

	i64 ans = -(1ll << 60);
	i64 ansp = x1;

	int y = (y1 + y2) / 2;

	for (int i = x1; i <= x2; i++)
	{
		i64 v = get(y, i);
		if (v > ans)
		{
			ans = v;
			ansp = i;
		}
	}

	big[y] = ans;

	f(y1, y - 1, x1, ansp);
	f(y + 1, y2, ansp, x2);
}

i64 solve()
{
	for (int i = 0; i < n; i++)
		big[i] = -(1ll << 60);

	vector<ii64> byVal;
	for (int i = 0; i < n; i++)
		byVal.emplace_back(arr[i], i);

	sort(all(byVal));

	vector<int> order(n);
	for (int i = 0; i < n; i++)
		order[byVal[i].yy] = i + 1;

	tree = PST(100005, [](const Pt& l, const Pt& r) { return Pt(l.xx + r.xx, l.yy + r.yy); });
	tree.init();

	for (int i = 0; i < n; i++)
		tree.update(order[i], Pt(arr[i], 1));

	f(1, s, 1, n);

	i64 ans = big[1];

	for (int i = 1; i <= n; i++)
		ans = max(ans, big[i]);

	return ans;
}


long long int findMaxAttraction(int n_, int s_, int d_, int attraction[])
{
	n = n_;
	s = s_ + 1;
	d = d_;
 
	arr.resize(n);
	for (int i = 0; i < n; i++)
		arr[i] = attraction[i];
 
	i64 ans = solve();
	reverse(all(arr));
	s = n + 1 - s;
 
	i64 ans2 = solve();
 
	return max(ans, ans2);
}

Compilation message (stderr)

holiday.cpp: In constructor 'Node::Node()':
holiday.cpp:31:5: warning: 'Node::value' will be initialized after [-Wreorder]
   31 |  Pt value;
      |     ^~~~~
holiday.cpp:30:6: warning:   'int Node::lidx' [-Wreorder]
   30 |  int lidx, ridx;
      |      ^~~~
holiday.cpp:33:2: warning:   when initialized here [-Wreorder]
   33 |  Node() :value(Pt()), lidx(-1), ridx(-1) {}
      |  ^~~~
holiday.cpp: In instantiation of 'PST::PST(int, const M&) [with M = <lambda(const Pt&, const Pt&)>]':
holiday.cpp:172:94:   required from here
holiday.cpp:167:6: warning: 'PST::n' will be initialized after [-Wreorder]
  167 |  int n;
      |      ^
holiday.cpp:165:8: warning:   'PST::Merge PST::merge' [-Wreorder]
  165 |  Merge merge;
      |        ^~~~~
holiday.cpp:75:2: warning:   when initialized here [-Wreorder]
   75 |  PST(int n_, const M& m) : n(n_), merge(m)
      |  ^~~
holiday.cpp: In instantiation of 'PST::PST(int, const M&) [with M = solve()::<lambda(const Pt&, const Pt&)>]':
holiday.cpp:262:90:   required from here
holiday.cpp:167:6: warning: 'PST::n' will be initialized after [-Wreorder]
  167 |  int n;
      |      ^
holiday.cpp:165:8: warning:   'PST::Merge PST::merge' [-Wreorder]
  165 |  Merge merge;
      |        ^~~~~
holiday.cpp:75:2: warning:   when initialized here [-Wreorder]
   75 |  PST(int n_, const M& m) : n(n_), merge(m)
      |  ^~~

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