Submission #49534

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49534	2018-05-31T00:07:29 Z	tmwilliamlin168	Divide and conquer (IZhO14_divide)	C++14	100 / 100	85 ms	4144 KB

divide

#include <bits/stdc++.h>
using namespace std;

#define ll long long

inline int in() {
	int result = 0;
	char ch = getchar_unlocked();
	while (true) {
		if(ch >= '0' && ch <= '9')
			break;
		ch = getchar_unlocked();
	}
	result = ch-'0';
	while(true) {
		ch = getchar_unlocked();
		if (ch < '0' || ch > '9')
			break;
		result = result*10 + (ch - '0');
	}
	return result;
}
inline void out(ll x) {
	ll rev=x;
	int count = 0;
	while((rev % 10) == 0) {
++count;
rev /= 10;
} //obtain the count of the number of 0s
	rev = 0;
	while(x != 0) {
rev = rev*10 + x % 10;
x /= 10;
} //store reverse of N in rev
	while(rev != 0) {
putchar_unlocked(rev % 10 + '0');
rev /= 10;
}
	while(count--)
putchar_unlocked('0');
}

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	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	408 KB	Output is correct
4	Correct	2 ms	484 KB	Output is correct
5	Correct	2 ms	560 KB	Output is correct
6	Correct	2 ms	560 KB	Output is correct
7	Correct	2 ms	560 KB	Output is correct
8	Correct	2 ms	608 KB	Output is correct
9	Correct	3 ms	696 KB	Output is correct
10	Correct	2 ms	696 KB	Output is correct
11	Correct	2 ms	696 KB	Output is correct
12	Correct	2 ms	696 KB	Output is correct

Subtask #2

31.0 / 31.0

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

Subtask #3

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	748 KB	Output is correct
2	Correct	7 ms	880 KB	Output is correct
3	Correct	7 ms	880 KB	Output is correct
4	Correct	31 ms	2412 KB	Output is correct
5	Correct	33 ms	2412 KB	Output is correct
6	Correct	63 ms	4092 KB	Output is correct
7	Correct	55 ms	4092 KB	Output is correct
8	Correct	55 ms	4092 KB	Output is correct
9	Correct	52 ms	4092 KB	Output is correct
10	Correct	57 ms	4140 KB	Output is correct
11	Correct	69 ms	4140 KB	Output is correct
12	Correct	85 ms	4144 KB	Output is correct