Submission #49535

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49535	2018-05-31T00:08:20 Z	tmwilliamlin168	Divide and conquer (IZhO14_divide)	C++14	100 / 100	38 ms	4096 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() {
	n=in();
	for(int i=0; i<n; ++i) {
		x[i]=in(), pg[i+1]=in()+pg[i], pd[i+1]=in()+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);
	}
	out(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	416 KB	Output is correct
4	Correct	2 ms	492 KB	Output is correct
5	Correct	11 ms	492 KB	Output is correct
6	Correct	2 ms	544 KB	Output is correct
7	Correct	2 ms	672 KB	Output is correct
8	Correct	2 ms	672 KB	Output is correct
9	Correct	2 ms	672 KB	Output is correct
10	Correct	2 ms	672 KB	Output is correct
11	Correct	2 ms	672 KB	Output is correct
12	Correct	3 ms	744 KB	Output is correct

Subtask #2

31.0 / 31.0

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

Subtask #3

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	768 KB	Output is correct
2	Correct	4 ms	896 KB	Output is correct
3	Correct	4 ms	896 KB	Output is correct
4	Correct	15 ms	2300 KB	Output is correct
5	Correct	16 ms	2356 KB	Output is correct
6	Correct	31 ms	4092 KB	Output is correct
7	Correct	27 ms	4092 KB	Output is correct
8	Correct	28 ms	4096 KB	Output is correct
9	Correct	29 ms	4096 KB	Output is correct
10	Correct	30 ms	4096 KB	Output is correct
11	Correct	38 ms	4096 KB	Output is correct
12	Correct	33 ms	4096 KB	Output is correct