oj.uz

Submission #49533

# Submission time Handle Problem Language Result Execution time Memory
49533 2018-05-30T23:52:15 Z tmwilliamlin168 Divide and conquer (IZhO14_divide) C++14
100 / 100
 86 ms 22640 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN=1e5;
int n, x[mxN];
ll pg[mxN+1], pd[mxN+1], pts[mxN], ft[mxN+1], ans;

inline void upd(int i, ll x) {
	for(++i; i<=n; i+=i&-i)
		ft[i]=max(x, ft[i]);
}

inline ll qry(int i) {
	ll r=0;
	for(; i; i-=i&-i)
		r=max(ft[i], r);
	return r;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for(int i=0; i<n; ++i) {
		cin >> x[i] >> pg[i+1] >> pd[i+1], pg[i+1]+=pg[i], pd[i+1]+=pd[i];
		pts[i]=x[i]-pd[i+1];
	}
	sort(pts, pts+n);
	for(int i=n-1; i>=0; --i) {
		upd(lower_bound(pts, pts+n, x[i]-pd[i+1])-pts, pg[i+1]);
		ans=max(qry(upper_bound(pts, pts+n, x[i]-pd[i])-pts)-pg[i], ans);
	}
	cout << ans;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 880 KB Output is correct
2 Correct 2 ms 880 KB Output is correct
3 Correct 2 ms 924 KB Output is correct
4 Correct 2 ms 952 KB Output is correct
5 Correct 3 ms 984 KB Output is correct
6 Correct 6 ms 1268 KB Output is correct
7 Correct 3 ms 1268 KB Output is correct
8 Correct 3 ms 1268 KB Output is correct
9 Correct 4 ms 1268 KB Output is correct
10 Correct 3 ms 1328 KB Output is correct
11 Correct 6 ms 1496 KB Output is correct
12 Correct 5 ms 1608 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1732 KB Output is correct
2 Correct 10 ms 1992 KB Output is correct
3 Correct 8 ms 2252 KB Output is correct
4 Correct 29 ms 4700 KB Output is correct
5 Correct 30 ms 6012 KB Output is correct
6 Correct 74 ms 10692 KB Output is correct
7 Correct 57 ms 12536 KB Output is correct
8 Correct 58 ms 14500 KB Output is correct
9 Correct 59 ms 16288 KB Output is correct
10 Correct 54 ms 18020 KB Output is correct
11 Correct 59 ms 20260 KB Output is correct
12 Correct 86 ms 22640 KB Output is correct