Submission #1265910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265910		canhnam357	Divide and conquer (IZhO14_divide)	C++20	100 / 100	36 ms	3144 KiB

divide

// source problem : 
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define int long long
#define lb lower_bound
#define ub upper_bound
#define MASK(i) (1LL << (i))
const int inf = 1e18;
void ckmax(int& f, int s)
{
	f = (f > s ? f : s);
}
void ckmin(int& f, int s)
{
	f = (f < s ? f : s);
}
vector<int> st(1 << 18, -inf);
void update(int pos, int x, int id = 1, int l = 1, int r = 1 << 17)
{
	if (pos < l || pos > r) return;
	if (l == r)
	{
		st[id] = x;
		return;
	}
	int mid = (l + r) >> 1;
	update(pos, x, id << 1, l, mid);
	update(pos, x, id << 1 | 1, mid + 1, r);
	st[id] = max(st[id << 1], st[id << 1 | 1]);
}
int find(int x, int id = 1, int l = 1, int r = 1 << 17)
{
	if (l == r) return l;
	int mid = (l + r) >> 1;
	if (st[id << 1] >= x) return find(x, id << 1, l, mid);
	return find(x, id << 1 | 1, mid + 1, r);
}
struct fenwick
{
	int n;
	vector<int> bit;
	fenwick() {}
	fenwick(int n)
	{
		this->n = n + 5;
		bit.resize(n + 5);
	}
	void add(int pos, int val)
	{
		while (pos < n)
		{
			bit[pos] += val;
			pos += pos & -pos;
		}
	}
	int get(int pos)
	{
		int ans = 0;
		while (pos)
		{
			ans += bit[pos];
			pos -= pos & -pos;
		}
		return ans;
	}
	int get(int l, int r)
	{
		return get(r) - get(l - 1);
	}
	int find(int k)
	{
		int sum = 0, pos = 0;
		for (int i = __lg(n); i >= 0; i--)
		{
			if (pos + (1 << i) < n && sum + bit[pos + (1 << i)] < k)
			{
				sum += bit[pos + (1 << i)];
				pos += (1 << i);
			}
		}
		return pos + 1;
	}
};
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	/*
	xj - xi <= pre[j] - pre[i - 1]
	i nhỏ nhất mà xj - pre[j] <= xi - pre[i - 1]
	*/	
	int n;
	cin >> n;
	fenwick tree(n);
	int p = 0, ans = 0;
	for (int i = 1; i <= n; i++)
	{
		int x, g, d;
		cin >> x >> g >> d;
		tree.add(i, g);
		update(i, x - p);
		p += d;
		int k = find(x - p);
		ckmax(ans, tree.get(k, i));
	}
	cout << ans;
	return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52