제출 #473086

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
473086		jwvg0425	휴가 (IOI14_holiday)	C++17	24 / 100	392 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;
};
 
int n, s, d;
auto tree = PST<ii64>(100005, [](const ii64& l, const ii64& r) { return ii64(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[200005];
 
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<ii64>(100005, [](const ii64& l, const ii64& r) { return ii64(l.xx + r.xx, l.yy + r.yy); });
	tree.init();
 
	for (int i = 0; i < n; i++)
		tree.update(order[i], ii64(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);
}

컴파일 시 표준 에러 (stderr) 메시지

holiday.cpp: In instantiation of 'PST<T>::PST(int, const M&) [with M = <lambda(const ii64&, const ii64&)>; T = std::pair<long long int, long long int>]':
holiday.cpp:169:106:   required from here
holiday.cpp:165:6: warning: 'PST<std::pair<long long int, long long int> >::n' will be initialized after [-Wreorder]
  165 |  int n;
      |      ^
holiday.cpp:162:8: warning:   'PST<std::pair<long long int, long long int> >::Merge PST<std::pair<long long int, long long 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 ii64&, const ii64&)>; T = std::pair<long long int, long long int>]':
holiday.cpp:259:102:   required from here
holiday.cpp:165:6: warning: 'PST<std::pair<long long int, long long int> >::n' will be initialized after [-Wreorder]
  165 |  int n;
      |      ^
holiday.cpp:162:8: warning:   'PST<std::pair<long long int, long long int> >::Merge PST<std::pair<long long int, long long 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, long long 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, long long int> >::Node; _Args = {}; _Tp = PST<std::pair<long long int, long long 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, long long int> >::Node; _Args = {}; _Tp = PST<std::pair<long long int, long long int> >::Node; std::allocator_traits<std::allocator<_Tp1> >::allocator_type = std::allocator<PST<std::pair<long long int, long long 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, long long int> >::Node; _Alloc = std::allocator<PST<std::pair<long long int, long long int> >::Node>; std::vector<_Tp, _Alloc>::reference = PST<std::pair<long long int, long long int> >::Node&]'
holiday.cpp:111:20:   required from 'int PST<T>::init(int, int) [with T = std::pair<long long int, long long int>]'
holiday.cpp:104:22:   required from 'void PST<T>::init() [with T = std::pair<long long int, long long int>]'
holiday.cpp:260:12:   required from here
holiday.cpp:34:5: warning: 'PST<std::pair<long long int, long long int> >::Node::value' will be initialized after [-Wreorder]
   34 |   T value;
      |     ^~~~~
holiday.cpp:33:7: warning:   'int PST<std::pair<long long int, long long 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