Submission #344643

#	Time	Username	Problem	Language	Result	Execution time	Memory
344643		l3nl3	Divide and conquer (IZhO14_divide)	C++14	100 / 100	55 ms	6252 KiB

divide

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>  

#define exit exit(false)

//#define here() cerr << "herewego\n";
#define show(x) cerr << #x << ": " << x << '\n';

#define int long long
//#define double long double

#define all(a) a.begin(), a.end()
#define whole(a, p, q) a+p, a+p+q

#define ioio() ios_base::sync_with_stdio (0); cin.tie (0); cout.tie (0);

using namespace std;

//using namespace __gnu_pbds;   
//typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;  

const int sz = 100007;

int n, x[sz], g[sz], d[sz], p[sz], pp[sz], mx, mxx, t[sz*4];

void upd (int v, int tl, int tr, int val, int pos) {
	if (tl == tr) {
		t[v] = val;
		return;
	}
	int tm = (tl + tr) >> 1;
	int lf = (v << 1);
	int rg = (v << 1 | 1);
	if (pos <= tm) {
		upd (lf, tl, tm, val, pos);		
	} else {
		upd (rg, tm+1, tr, val, pos);
	}
	t[v] = max (t[lf], t[rg]);
}

void upd (int val, int pos) {
	return upd (1, 1, n, val, pos);
}

int get (int v, int tl, int tr, int val) {
	if (tl == tr) {
		return tl;
	}
	int tm = (tl + tr) >> 1;
	int lf = (v << 1);
	int rg = (v << 1 | 1);
	if (t[rg] >= val) {
		return get (rg, tm+1, tr, val);
	}
	return get (lf, tl, tm, val);
}

int get (int val) {
	return get (1, 1, n, val);
}

signed main () { ioio();
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x[i] >> g[i] >> d[i];
		p[i] = p[i-1] + d[i];
		pp[i] = pp[i-1] + g[i];
		upd (p[i] - x[i], i);
	}
	for (int i = 1; i <= n; i++) {
		int e = get (p[i-1] - x[i]);
//		show(e);
		mx = max (mx, pp[e] - pp[i-1]);
	}
	cout << mx;
}

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