Submission #471078

#	Time	Username	Problem	Language	Result	Execution time	Memory
471078		jwvg0425	Cake 3 (JOI19_cake3)	C++17	100 / 100	959 ms	114264 KiB

cake3

#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, m;
auto tree = PST<ii64>(200005, [](const ii64& l, const ii64& r) { return ii64(l.xx + r.xx, l.yy + r.yy); });
vector<ii64> cakes;

i64 get(int l, int r)
{
	if (r - l < m - 1)
		return  -(1ll << 60) + r + 1;

	i64 res = cakes[l].xx + cakes[r].xx - 2 * (cakes[r].yy - cakes[l].yy);
	auto lx = tree.it(l + 1);
	auto rx = tree.it(r);

	int s = 0, e = 200005;
	int need = m - 2;

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

int main()
{
    scanf("%d %d", &n, &m);

	cakes.resize(n);
    for (int i = 0; i < n; i++)
        scanf("%lld %lld", &cakes[i].xx, &cakes[i].yy);

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

    sort(all(cakes), [](const ii64& l, const ii64& r)
    {
        return l.yy < r.yy;
    });

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

	sort(all(byVal));

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

	tree.init();

	for (int i = 0; i < n; i++)
		tree.update(order[i], ii64(cakes[i].xx, 1));

    f(0, n - 1, 0, n - 1);

    i64 ans = big[0];

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

    printf("%lld\n", ans);

    return 0;
}

Compilation message (stderr)

cake3.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>]':
cake3.cpp:168:106:   required from here
cake3.cpp:164:6: warning: 'PST<std::pair<long long int, long long int> >::n' will be initialized after [-Wreorder]
  164 |  int n;
      |      ^
cake3.cpp:161:8: warning:   'PST<std::pair<long long int, long long int> >::Merge PST<std::pair<long long int, long long int> >::merge' [-Wreorder]
  161 |  Merge merge;
      |        ^~~~~
cake3.cpp:73:2: warning:   when initialized here [-Wreorder]
   73 |  PST(int n_, const M& m) : n(n_), merge(m) {}
      |  ^~~
cake3.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&]'
cake3.cpp:110:20:   required from 'int PST<T>::init(int, int) [with T = std::pair<long long int, long long int>]'
cake3.cpp:103:22:   required from 'void PST<T>::init() [with T = std::pair<long long int, long long int>]'
cake3.cpp:267:12:   required from here
cake3.cpp:33:5: warning: 'PST<std::pair<long long int, long long int> >::Node::value' will be initialized after [-Wreorder]
   33 |   T value;
      |     ^~~~~
cake3.cpp:32:7: warning:   'int PST<std::pair<long long int, long long int> >::Node::lidx' [-Wreorder]
   32 |   int lidx, ridx;
      |       ^~~~
cake3.cpp:35:3: warning:   when initialized here [-Wreorder]
   35 |   Node() :value(T()), lidx(-1), ridx(-1) {}
      |   ^~~~
cake3.cpp: In function 'int main()':
cake3.cpp:243:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  243 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
cake3.cpp:247:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  247 |         scanf("%lld %lld", &cakes[i].xx, &cakes[i].yy);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76