oj.uz

Submission #68472

# Submission time Handle Problem Language Result Execution time Memory
68472 2018-08-17T07:55:26 Z quoriess Divide and conquer (IZhO14_divide) C++14
100 / 100
 380 ms 25176 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pii;
struct data{
	lli x, energy, gold;
	data(lli _x,lli _energy,lli _gold){
		x=_x;
		energy=_energy;
		gold=_gold;
	}
	bool operator <(data other){
		return x<other.x;
	}
};
const lli MAXN=1e5+5;
lli segmentTree[8*MAXN];
/*
8 10
7 3 5 12 2 7 3 4
 * */
void buildTree(lli node,lli a,lli b){
	if(a==b)segmentTree[node]=1e10;
	else
	{
		buildTree(node*2,a,(a+b)/2);
		buildTree(node*2+1,(a+b)/2+1,b);
		segmentTree[node]=min(segmentTree[node*2],segmentTree[node*2+1]);
	}
}
void updateTree(lli node,lli a,lli b,lli i,lli x){
	//cout << "update: "<<node<<" " <<a <<" "<<b<< " " <<i<<" "<<x<<"\n";
	if(a>b||a>i||b<i)return;
	if(a==b&&a==i)segmentTree[node]=min(x,segmentTree[node]);
	else{
		updateTree(node*2,a,(a+b)/2,i,x);
		updateTree(node*2+1,(a+b)/2+1,b,i,x);
		segmentTree[node]=min(segmentTree[node*2],segmentTree[node*2+1]);
	}
}
lli queryTree(lli node,lli a,lli b,lli l,lli r){
	if(a>b||a>r||b<l)return 1e7;
	if(a>=l&&b<=r)return segmentTree[node];
	lli q1=queryTree(node*2,a,(a+b)/2,l,r);
	lli q2=queryTree(node*2+1,(a+b)/2+1,b,l,r);
	return min(q1,q2);
}
vector<data> datas;
int main(){
	lli n;
	cin>>n;
	for (lli i = 0; i < n; i++)
	{
		lli a,b,c;
		cin>>a>>b>>c;
		data d(a,c,b);
		datas.push_back(d);
	}
	lli pre[n];
	lli goldpre[n];
	pre[0]=datas[0].energy;
	goldpre[0]=datas[0].gold;
	for (lli i = 1; i < n; i++)
	{
		pre[i]=pre[i-1]+datas[i].energy;
		goldpre[i]=goldpre[i-1]+datas[i].gold;
	}
	//pii olması gereksiz
	vector<pii> tbnrm;
	tbnrm.push_back(pii(-datas[0].x,0));
	for (lli i = 1; i < n; i++)
	{
		tbnrm.push_back(pii(pre[i-1]-datas[i].x,i));
		tbnrm.push_back(pii(pre[i]-datas[i].x,i));
	}
	sort(tbnrm.begin(),tbnrm.end());
	lli sr=0;
	map<lli,lli> normalized;
	lli ans=goldpre[0];
	for(auto u:tbnrm){
		if(normalized.find(u.first)==normalized.end()){
			normalized[u.first]=sr;
			sr++;
		}
	}
	buildTree(1,0,2*n-1);
	updateTree(1,0,2*n-1,normalized[-datas[0].x],0);
	lli dp[n];
	dp[0]=goldpre[0];
	for (lli i = 1; i < n; i++)
	{
		lli qry=queryTree(1,0,2*n-1,0,normalized[pre[i]-datas[i].x]);
		dp[i]=qry;
		updateTree(1,0,2*n-1,normalized[pre[i-1]-datas[i].x],i);
	}
	for (lli i = 1; i < n; i++)
	{
	    if(dp[i]<1e7)
		ans=max(goldpre[i]-(dp[i]>0?goldpre[dp[i]-1]:0),ans);
        else ans=max(datas[i].gold,ans);
	}
	cout<<ans<<"\n";
	return 0;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 3 ms 708 KB Output is correct
4 Correct 4 ms 832 KB Output is correct
5 Correct 5 ms 832 KB Output is correct
6 Correct 7 ms 876 KB Output is correct
7 Correct 4 ms 876 KB Output is correct
8 Correct 4 ms 876 KB Output is correct
9 Correct 5 ms 948 KB Output is correct
10 Correct 6 ms 1096 KB Output is correct
11 Correct 15 ms 1844 KB Output is correct
12 Correct 18 ms 1908 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1908 KB Output is correct
2 Correct 27 ms 3188 KB Output is correct
3 Correct 33 ms 3188 KB Output is correct
4 Correct 153 ms 12768 KB Output is correct
5 Correct 174 ms 12932 KB Output is correct
6 Correct 371 ms 25176 KB Output is correct
7 Correct 380 ms 25176 KB Output is correct
8 Correct 359 ms 25176 KB Output is correct
9 Correct 341 ms 25176 KB Output is correct
10 Correct 352 ms 25176 KB Output is correct
11 Correct 371 ms 25176 KB Output is correct
12 Correct 366 ms 25176 KB Output is correct