Submission #116760

#	Time	Username	Problem	Language	Result	Execution time	Memory
116760		roseanne_pcy	Divide and conquer (IZhO14_divide)	C++14	100 / 100	79 ms	8812 KiB

divide

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 1e5+5;

ll st[4*maxn];

int m;

void build(int p = 1, int L = 0, int R = m-1)
{
	if(L == R)
	{
		st[p] = 4e18;
		return;
	}
	int M = (L+R)/2;
	build(2*p, L, M);
	build(2*p+1, M+1, R);
	st[p] = 4e18;
}
void update(int x, ll dx, int p = 1, int L = 0, int R = m-1)
{
	if(L == R)
	{
		st[p] = min(st[p], dx);
		return;
	}
	int M = (L+R)/2;
	if(x<= M) update(x, dx, 2*p, L, M);
	else update(x, dx, 2*p+1, M+1, R);
	st[p] = min(st[2*p], st[2*p+1]);
}

ll ask(int i, int j, int p = 1, int L = 0, int R = m-1)
{
	if(i> R || j< L) return 4e18;
	if(i<= L && R<= j) return st[p];
	int M = (L+R)/2;
	ll x = ask(i, j, 2*p, L, M);
	ll y = ask(i, j, 2*p+1, M+1, R);
	return min(x, y);
}

ll x[maxn], g[maxn], d[maxn];

int n;

int main()
{
	scanf("%d", &n);
	for(int i = 1; i<= n; i++) scanf("%lld %lld %lld", &x[i], &g[i], &d[i]);
	for(int i = 1; i<= n; i++)
	{
		g[i] += g[i-1];
		d[i] += d[i-1];
	}
	vector<ll> det;
	for(int i = 1; i<= n; i++) det.pb(d[i-1]-x[i]);
	sort(det.begin(), det.end());
	det.erase(unique(det.begin(), det.end()), det.end());
	m = det.size();
	build();
	// printf("%lld\n", ask(0, m-1));
	ll opt = 0;
	for(int i = 1; i<= n; i++)
	{
		int pos = lower_bound(det.begin(), det.end(), d[i-1]-x[i])-det.begin();
		update(pos, g[i-1]);
		int lim = upper_bound(det.begin(), det.end(), d[i]-x[i])-det.begin()-1;
		ll best = ask(0, lim);
		opt = max(opt, g[i]-best);
	}
	printf("%lld\n", opt);
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
divide.cpp:59:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i<= n; i++) scanf("%lld %lld %lld", &x[i], &g[i], &d[i]);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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