Submission #259412

#	Time	Username	Problem	Language	Result	Execution time	Memory
259412		ChrisT	Divide and conquer (IZhO14_divide)	C++17	100 / 100	78 ms	8808 KiB

divide

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int MN = 2e5 + 5, LOG = 18, MOD = 1e9 + 7;
ll bit[MN];
vector<ll> xs;
int getx (ll x) {return lower_bound(xs.begin(),xs.end(),x) - xs.begin() + 1;}
ll x[MN], g[MN], e[MN];
void update (int i, ll v) {
	for (i=MN-i;i<MN;i+=i&-i)
		bit[i] = min(bit[i],v);
}
ll query (int i) {
	ll ret = 1e18;
	for (i=MN-i;i;i^=i&-i)
		ret = min(ret,bit[i]);
	return ret;
}
int main () {
	int n;
	scanf ("%d",&n);
	for (int i = 1; i <= n; i++) {
		scanf ("%lld %lld %lld",&x[i],&g[i],&e[i]);
		g[i] += g[i-1]; e[i] += e[i-1];
		xs.push_back(x[i]-e[i]); xs.push_back(x[i]-e[i-1]);
	}
	sort(xs.begin(),xs.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end());
	memset(bit,0x3f,sizeof bit); ll ret = -1e18;
	for (int i = 1; i <= n; i++) {
		update(getx(x[i]-e[i-1]),g[i-1]);
		ret = max(ret,g[i] - query(getx(x[i]-e[i])));
	}
	printf ("%lld\n",ret);
	return 0;
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d",&n);
  ~~~~~~^~~~~~~~~
divide.cpp:24:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%lld %lld %lld",&x[i],&g[i],&e[i]);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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