Submission #68472

#	Time	Username	Problem	Language	Result	Execution time	Memory
68472		quoriess	Divide and conquer (IZhO14_divide)	C++14	100 / 100	380 ms	25176 KiB

divide

#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 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52