Submission #473089

#	Time	Username	Problem	Language	Result	Execution time	Memory
473089		jwvg0425	Holiday (IOI14_holiday)	C++17	24 / 100	382 ms	65540 KiB

holiday

#include "holiday.h"
#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>;

template<typename T>
class PST
{
	struct Node
	{
		int lidx, ridx;
		T value;

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

public:
	class iterator
	{
	public:
		iterator(PST<T>& p, int n)
			: pst(p), node(n) {}

		iterator& operator=(const iterator& other)
		{
			assert(&pst == &other.pst);
			node = other.node;
			return *this;
		}

		T get() const
		{
			return pst.node[node].value;
		}

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

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

	private:
		PST<T>& pst;
		int node;
	};

	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 T& value)
	{
		return update((int)root.size() - 1, idx, value);
	}

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

	T 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 = node.size();
		node.emplace_back();

		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 T& value, int start, int end)
	{
		if (idx < start || idx > end)
			return prev;

		int nidx = node.size();
		node.emplace_back();

		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;
	}

	T _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<T(const T&, const T&)>;
	Merge merge;
	vector<int> root;
	vector<Node> node;
	int n;
};

using Pt = pair<i64, int>;
int n, s, d;
auto tree = PST<Pt>(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<Pt>(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 instantiation of 'PST<T>::PST(int, const M&) [with M = <lambda(const Pt&, const Pt&)>; T = std::pair<long long int, int>]':
holiday.cpp:170:98:   required from here
holiday.cpp:165:6: warning: 'PST<std::pair<long long int, int> >::n' will be initialized after [-Wreorder]
  165 |  int n;
      |      ^
holiday.cpp:162:8: warning:   'PST<std::pair<long long int, int> >::Merge PST<std::pair<long long int, int> >::merge' [-Wreorder]
  162 |  Merge merge;
      |        ^~~~~
holiday.cpp:74:2: warning:   when initialized here [-Wreorder]
   74 |  PST(int n_, const M& m) : n(n_), merge(m) {}
      |  ^~~
holiday.cpp: In instantiation of 'PST<T>::PST(int, const M&) [with M = solve()::<lambda(const Pt&, const Pt&)>; T = std::pair<long long int, int>]':
holiday.cpp:260:94:   required from here
holiday.cpp:165:6: warning: 'PST<std::pair<long long int, int> >::n' will be initialized after [-Wreorder]
  165 |  int n;
      |      ^
holiday.cpp:162:8: warning:   'PST<std::pair<long long int, int> >::Merge PST<std::pair<long long int, int> >::merge' [-Wreorder]
  162 |  Merge merge;
      |        ^~~~~
holiday.cpp:74:2: warning:   when initialized here [-Wreorder]
   74 |  PST(int n_, const M& m) : n(n_), merge(m) {}
      |  ^~~
holiday.cpp: In instantiation of 'PST<T>::Node::Node() [with T = std::pair<long long int, int>]':
/usr/include/c++/10/ext/new_allocator.h:150:4:   required from 'void __gnu_cxx::new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = PST<std::pair<long long int, int> >::Node; _Args = {}; _Tp = PST<std::pair<long long int, int> >::Node]'
/usr/include/c++/10/bits/alloc_traits.h:512:17:   required from 'static void std::allocator_traits<std::allocator<_Tp1> >::construct(std::allocator_traits<std::allocator<_Tp1> >::allocator_type&, _Up*, _Args&& ...) [with _Up = PST<std::pair<long long int, int> >::Node; _Args = {}; _Tp = PST<std::pair<long long int, int> >::Node; std::allocator_traits<std::allocator<_Tp1> >::allocator_type = std::allocator<PST<std::pair<long long int, int> >::Node>]'
/usr/include/c++/10/bits/vector.tcc:115:30:   required from 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {}; _Tp = PST<std::pair<long long int, int> >::Node; _Alloc = std::allocator<PST<std::pair<long long int, int> >::Node>; std::vector<_Tp, _Alloc>::reference = PST<std::pair<long long int, int> >::Node&]'
holiday.cpp:111:20:   required from 'int PST<T>::init(int, int) [with T = std::pair<long long int, int>]'
holiday.cpp:104:22:   required from 'void PST<T>::init() [with T = std::pair<long long int, int>]'
holiday.cpp:261:12:   required from here
holiday.cpp:34:5: warning: 'PST<std::pair<long long int, int> >::Node::value' will be initialized after [-Wreorder]
   34 |   T value;
      |     ^~~~~
holiday.cpp:33:7: warning:   'int PST<std::pair<long long int, int> >::Node::lidx' [-Wreorder]
   33 |   int lidx, ridx;
      |       ^~~~
holiday.cpp:36:3: warning:   when initialized here [-Wreorder]
   36 |   Node() :value(T()), lidx(-1), ridx(-1) {}
      |   ^~~~

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