Submission #223067

#	Time	Username	Problem	Language	Result	Execution time	Memory
223067		staniewzki	Holiday (IOI14_holiday)	C++17	30 / 100	1064 ms	11284 KiB

holiday

#include<bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
 
ostream& operator<<(ostream &out, string str) {
	for(char c : str) out << c;
	return out;
}
 
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
	return out << "(" << p.ST << ", " << p.ND << ")";
}
 
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
	out << "{";
	for(auto it = a.begin(); it != a.end(); it = next(it))
		out << (it != a.begin() ? ", " : "") << *it;
	return out << "}";
}
 
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
	cerr << a << ", ";
	dump(x...);
}
 
#ifdef DEBUG
#  define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#  define debug(...) false
#endif
 
template<class T> int size(T && a) { return (int) a.size(); }
 
using LL = long long;
using PII = pair<int, int>;

#include"holiday.h"

struct SegTree {
	using T = pair<LL, int>;
	vector<T> tree;
	int sz = 1;

	T f(T a, T b) {
		T ret = {0, 0};
		if(a.ND != 0) {
			ret.ST += a.ST;
			ret.ND += a.ND;
		}
		if(b.ND != 0) {
			ret.ST += b.ST;
			ret.ND += b.ND;
		}
		return ret;
	}

	SegTree(vector<int> a) {
		int n = size(a);
		while(sz < n) sz *= 2;
		tree.resize(sz * 2);
		REP(i, n) tree[i + sz].ST = a[i];
	}

	void update(int v, int q) {
		tree[v += sz].ND = q;
		while(v /= 2)
			tree[v] = f(tree[v * 2], tree[v * 2 + 1]);
	}

	LL query(int k) {
		int v = 1;
		LL ret = 0;
		while(v < sz) {
			if(k < tree[v * 2].ND) v *= 2;
			else {
				k -= tree[v * 2].ND;
				if(tree[v * 2].ND)
					ret += tree[v * 2].ST;
				v = v * 2 + 1;
			}
		}
		return ret;
	}
};

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
	auto get_on_right = [&](int cost) {
		vector<int> a(n), per(n);
		REP(i, n) {
			a[i] = attraction[i];
			per[i] = i;
		}

		debug(a);

		sort(per.begin(), per.end(), [&](int i, int j) {
			return a[i] > a[j];
		});
		sort(a.rbegin(), a.rend());

		vector<int> ord(n);
		REP(i, n) ord[per[i]] = i;

		SegTree tree(a);

		vector<LL> ret(d + 1);
		auto solve = [&](auto self, int d_l, int d_r, int opt_l, int opt_r) {
			if(opt_l > opt_r) return;
			if(d_l > d_r) {
				FOR(i, opt_l, opt_r)
					tree.update(ord[i], true);
				return;
			}

			int cur_d = (d_l + d_r) / 2;
			pair<LL, int> best = {0, opt_l};
			FOR(i, opt_l, opt_r) {
				tree.update(ord[i], true);
				LL x = tree.query(cur_d - cost * (i - start));
				best = max(best, {x, i});
			}

			FOR(i, opt_l, opt_r)
				tree.update(ord[i], false);

			int opt = best.ND;
			ret[cur_d] = best.ST;

			self(self, d_l, cur_d - 1, opt_l, opt);
			tree.update(ord[opt], false);
			self(self, cur_d + 1, d_r, opt, opt_r);
		};

		solve(solve, 0, d, start + cost - 1, n - 1);

		FOR(i, start, n - 1)
			tree.update(ord[i], false);

		return ret;
	};

	auto rev = [&]() {
		reverse(attraction, attraction + n);
		start = n - 1 - start;
	};

	auto left_then_right = [&]() {
		auto A = get_on_right(1);
		rev();
		auto B = get_on_right(2);

		FOR(i, 0, d) 
			debug(i, A[i], B[i]);
		
		LL ret = 0;
		FOR(i, 0, d)
			ret = max(ret, A[i] + B[d - i]);
		return ret;
	};

	return max(left_then_right(), left_then_right());
}

Compilation message (stderr)

holiday.cpp: In lambda function:
holiday.cpp:99:11: warning: statement has no effect [-Wunused-value]
   debug(a);
           ^
holiday.cpp: In lambda function:
holiday.cpp:158:24: warning: statement has no effect [-Wunused-value]
    debug(i, A[i], B[i]);
                        ^

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