oj.uz

Submission #182426

# Submission time Handle Problem Language Result Execution time Memory
182426 2020-01-09T19:30:52 Z mahmoudbadawy Divide and conquer (IZhO14_divide) C++17
100 / 100
 277 ms 12532 KB 
#include <bits/stdc++.h>

using namespace std;

const int N=1e5+5;

int x[N],g[N],e[N];
long long gs[N],es[N],dp[N],btree[8*N];
int n;
vector<long long> cmp;

int get(long long x)
{
	return lower_bound(cmp.begin(),cmp.end(),x)-cmp.begin();
}

void update(int node,int l,int r,int ind,long long val)
{
	//if(ind<l||ind>r) return;
	if(l==r)
	{
		btree[node]=max(btree[node],val);
		return;
	}
	int mid=(l+r)/2;
	if(ind<=mid)
		update(node*2,l,mid,ind,val);
	else
		update(node*2+1,mid+1,r,ind,val);
	btree[node]=max(btree[node*2],btree[node*2+1]);
}

long long query(int node,int l,int r,int ql,int qr)
{
	if(r<ql||qr<l) return 0;
	if(ql<=l&&r<=qr) return btree[node];
	int mid=(l+r)/2;
	return max(query(node*2,l,mid,ql,qr),query(node*2+1,mid+1,r,ql,qr));
}

int main()
{
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		cin >> x[i] >> g[i] >> e[i];
		gs[i]=g[i]+gs[i-1];
		es[i]=e[i]+es[i-1];
		// e[j] - e[i-1] >= (x[j]-x[i])
		// e[j] - x[j] >= e[i-1]-x[i]
		cmp.push_back(es[i]-x[i]);
		cmp.push_back(es[i-1]-x[i]);
	}
	sort(cmp.begin(),cmp.end());
	cmp.erase(unique(cmp.begin(),cmp.end()),cmp.end());
	long long mx=0;
	for(int i=n;i>=1;i--)
	{
		mx=max(mx,1LL*g[i]);
		//cout << es[i-1]-x[i]+1 << " " << es[i]-x[i] << endl;
		dp[i]=max(mx,query(1,0,cmp.size()-1,get(es[i-1]-x[i]),cmp.size()-1)-gs[i-1]);
		//cout << dp[i] << endl;
		mx=max(mx,dp[i]);
		update(1,0,cmp.size()-1,get(es[i]-x[i]),gs[i]);
	}
	cout << dp[1] << endl;
}

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 376 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 380 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 420 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 3 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 5 ms 476 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 4 ms 504 KB Output is correct
8 Correct 4 ms 504 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 13 ms 1088 KB Output is correct
12 Correct 13 ms 1144 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1016 KB Output is correct
2 Correct 18 ms 1648 KB Output is correct
3 Correct 23 ms 1780 KB Output is correct
4 Correct 112 ms 6180 KB Output is correct
5 Correct 130 ms 6376 KB Output is correct
6 Correct 277 ms 12532 KB Output is correct
7 Correct 208 ms 11528 KB Output is correct
8 Correct 215 ms 11580 KB Output is correct
9 Correct 201 ms 11364 KB Output is correct
10 Correct 204 ms 11364 KB Output is correct
11 Correct 230 ms 11804 KB Output is correct
12 Correct 242 ms 12032 KB Output is correct