Submission #362755

#	Time	Username	Problem	Language	Result	Execution time	Memory
362755		hoaphat1	Holiday (IOI14_holiday)	C++17	24 / 100	1633 ms	65540 KiB

holiday

#include<bits/stdc++.h>
 
using namespace std;

struct Eins {
	struct node {
		long long val = 0;
		int cnt = 0;
		int lef = -1, rig = -1;
	};
	vector<node> st;
	int n;
	int count = 0;
	Eins(int n) : n(n) {
		st.resize(31 * n + 1);
	}
	void modify(int&id, int l, int r, int pos, int val) {
		if (id == -1) id = ++count;
		if (l == r) {
			st[id].val += pos * val;
			st[id].cnt += val;
			return ;
		}
		int mid = l + r >> 1;
		if (pos <= mid) modify(st[id].lef, l, mid, pos, val);
		else modify(st[id].rig, mid + 1, r, pos, val);
		st[id].val = st[id].cnt = 0;
		if (st[id].lef != -1) {
			st[id].val += st[st[id].lef].val;
			st[id].cnt += st[st[id].lef].cnt;
		}
		if (st[id].rig != -1) {
			st[id].val += st[st[id].rig].val;
			st[id].cnt += st[st[id].rig].cnt;
		}
	}
	long long get(int id, int l, int r, int& num) {
		if (id == -1) return 0;
		if (num >= st[id].cnt) {
			num -= st[id].cnt;
			return st[id].val;
		}
		if (l == r) return 0;
		int mid = l + r >> 1;
		return get(st[id].rig, mid + 1, r, num) + get(st[id].lef, l, mid, num);
	}
};

long long findMaxAttraction(int n, int s, int d, int a[]) {
	long long ans = 0;
  int L = 0, R = -1;
  Eins Tree(n);
  const int maxN = (int) 1e9;
  int root = 0;
  auto add = [&](int id) {
  	Tree.modify(root, 0, maxN, a[id], 1);
	};
	auto del = [&](int id) {
		Tree.modify(root, 0, maxN, a[id], -1);
	};
  auto moveL = [&](int l) {
  	while (L < l) del(L++);
  	while (L > l) add(--L);
	};
	auto moveR = [&](int r) {
		while (R < r) add(++R);
		while (R > r) del(R--);
	};
	function<void(int, int, int, int)> solve = [&](int l, int r, int L, int R) {
		if (l > r) return ;
		int mid = l + r >> 1;
		int pos = -1;
		moveR(L);
		moveL(mid);
		long long val = -1;
		for (int i = L; i <= R; i++) {
			moveR(i);
			int lim = d - min(s - mid, i - s) - (i - mid);
			long long now = Tree.get(0, 0, maxN, lim);
			if (val < now) {
				val = now;
				pos = i;
			}
		}
		ans = max(ans, val);
		assert(pos != -1);
		solve(l, mid - 1, L, pos);
		solve(mid + 1, r, pos, R);
	};
	solve(max(0, s - d), s, s, min(n - 1, s + d));
	return ans;
}

Compilation message (stderr)

holiday.cpp: In member function 'void Eins::modify(int&, int, int, int, int)':
holiday.cpp:24:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |   int mid = l + r >> 1;
      |             ~~^~~
holiday.cpp: In member function 'long long int Eins::get(int, int, int, int&)':
holiday.cpp:44:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |   int mid = l + r >> 1;
      |             ~~^~~
holiday.cpp: In lambda function:
holiday.cpp:71:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |   int mid = l + r >> 1;
      |             ~~^~~

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