Submission #153356

#	Time	Username	Problem	Language	Result	Execution time	Memory
153356		Vladden	Divide and conquer (IZhO14_divide)	C++14	100 / 100	103 ms	12408 KiB

divide

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define po(x) (1<<x)
#define schnell ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL)
#define forn(i,n) for(ll i = 1;i<=n;i++)
typedef long long ll;
typedef long double ld;
#define DIM 100007
#define DIM2 DIM*150
#define MODULO 998244353 
#define MAXN 1000000
#define MS 302
#define BigNumSize 250
#define AddLimit 151
const ll INF = 10E16;
const ll mask = po(9) - 1;
const ll base = 100000000000;
const ld eps = 0.0000001;
struct pp {
	ll fi, sc;
	bool const operator < (const pp& b) {
		if (fi == b.fi)return sc < b.sc;
		return fi < b.fi;
	}
	bool const operator > (const pp& b) {
		if (fi == b.fi)return sc > b.sc;
		return fi > b.fi;
	}
	bool const operator == (const pp& b) {
		if (fi == b.fi && sc == b.sc)return 1;
		return 0;
	}
};
bool const operator<(const pp& a, const pp& b) {
	if (a.fi == b.fi)return a.sc < b.sc;
	return a.fi < b.fi;
}
struct node {
	ll x, g, d;
};
ll n,res = 0,prefenr[DIM],tree[DIM*4],gold[DIM];
pp prefe[DIM], preftotree[DIM];
node A[DIM];
bool mc(pp av, pp bv) {
	return av.fi > bv.fi;
}
void treeupdate(ll t, ll tl, ll tr, pp v) {
	if (tr<v.sc || tl>v.sc)return;
	if (tr == tl) {
		tree[t] = v.fi;
		return;
	}
	ll tm = (tl + tr) / 2;
	treeupdate(t * 2 + 1, tl, tm, v);
	treeupdate(t * 2 + 2, tm + 1, tr, v);
	tree[t] = min(tree[t * 2 + 1], tree[t * 2 + 2]);
}
void buildtree(ll t, ll tl, ll tr) {
	if (tl == tr) {
		tree[t] = INF;
		return;
	}
	ll tm = (tl + tr) / 2;
	buildtree(t * 2 + 1, tl, tm);
	buildtree(t * 2 + 2, tm + 1, tr);
	tree[t] = INF;
}
ll treefind(ll t, ll tl, ll tr, ll L, ll R) {
	if (tl > R || L > tr)return INF;
	if (L <= tl && tr <= R) {
		return tree[t];
	}
	ll tm = (tl + tr) / 2;
	return min(treefind(t * 2 + 1, tl, tm, L, R), treefind(t * 2 + 2, tm + 1, tr, L, R));
}
bool mco(node a, node b) {
	return a.x < b.x;
}
int main() {
	schnell;
	cin >> n;
	buildtree(0, 1, n);
	forn(i, n)cin >> A[i].x >> A[i].g >> A[i].d;
	sort(A + 1, A + 1 + n, mco);
	ll start = A[1].x;
	A[n + 1].x = A[n].x;
	forn(i, n) {
		gold[i] = gold[i - 1] + A[i].g;
		prefe[i].fi = A[i].x - start - prefenr[i - 1] - A[i].d;
		prefenr[i] = prefenr[i - 1] + A[i].d;
		prefe[i].sc = i;
		preftotree[i].fi = prefe[i].fi + A[i + 1].x - A[i].x;
		preftotree[i].sc = i;
	}
	sort(prefe + 1, prefe + 1 + n,mc);
	sort(preftotree + 1, preftotree + 1 + n,mc);
	ll p = 1;
	forn(i, n) {
		while (p <= n && prefe[i].fi <= preftotree[p].fi) {
			treeupdate(0, 1, n, { gold[preftotree[p].sc],preftotree[p].sc });
			p++;
		}
		if (prefe[i].fi <= 0) {
			res = max(res, gold[prefe[i].sc]);
		}
		res = max(res, gold[prefe[i].sc] - treefind(0, 1, n, 1,prefe[i].sc));
	}
	cout << res << endl;	
}

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