oj.uz

Submission #153356

# Submission time Handle Problem Language Result Execution time Memory
153356 2019-09-13T15:47:22 Z Vladden Divide and conquer (IZhO14_divide) C++14
100 / 100
 103 ms 12408 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 508 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 4 ms 632 KB Output is correct
11 Correct 6 ms 1040 KB Output is correct
12 Correct 6 ms 888 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 888 KB Output is correct
2 Correct 10 ms 1400 KB Output is correct
3 Correct 11 ms 1500 KB Output is correct
4 Correct 46 ms 5880 KB Output is correct
5 Correct 49 ms 6264 KB Output is correct
6 Correct 103 ms 12408 KB Output is correct
7 Correct 94 ms 11212 KB Output is correct
8 Correct 92 ms 11308 KB Output is correct
9 Correct 92 ms 11128 KB Output is correct
10 Correct 97 ms 11128 KB Output is correct
11 Correct 100 ms 11612 KB Output is correct
12 Correct 94 ms 11896 KB Output is correct