oj.uz

Submission #68468

# Submission time Handle Problem Language Result Execution time Memory
68468 2018-08-17T07:50:55 Z quoriess Divide and conquer (IZhO14_divide) C++14
52 / 100
 429 ms 23040 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[4*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,n-1);
	updateTree(1,0,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,n-1,0,normalized[pre[i]-datas[i].x]);
		dp[i]=qry;
		updateTree(1,0,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
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 3 ms 620 KB Output is correct
7 Correct 3 ms 620 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Incorrect 3 ms 620 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 676 KB Output is correct
2 Correct 3 ms 676 KB Output is correct
3 Correct 4 ms 676 KB Output is correct
4 Incorrect 5 ms 724 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1704 KB Output is correct
2 Correct 31 ms 2788 KB Output is correct
3 Correct 35 ms 2916 KB Output is correct
4 Correct 202 ms 11916 KB Output is correct
5 Correct 242 ms 11916 KB Output is correct
6 Correct 429 ms 22992 KB Output is correct
7 Correct 415 ms 22992 KB Output is correct
8 Correct 374 ms 22992 KB Output is correct
9 Correct 343 ms 22992 KB Output is correct
10 Correct 366 ms 22992 KB Output is correct
11 Correct 362 ms 22992 KB Output is correct
12 Correct 385 ms 23040 KB Output is correct