oj.uz

Submission #68471

# Submission time Handle Problem Language Result Execution time Memory
68471 2018-08-17T07:53:34 Z quoriess Divide and conquer (IZhO14_divide) C++14
48 / 100
 358 ms 44232 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,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 2 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 4 ms 720 KB Output is correct
6 Correct 3 ms 720 KB Output is correct
7 Correct 3 ms 720 KB Output is correct
8 Correct 3 ms 720 KB Output is correct
9 Correct 3 ms 720 KB Output is correct
10 Correct 5 ms 720 KB Output is correct
11 Correct 3 ms 720 KB Output is correct
12 Correct 3 ms 720 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 720 KB Output is correct
2 Correct 2 ms 740 KB Output is correct
3 Correct 5 ms 740 KB Output is correct
4 Correct 5 ms 740 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 7 ms 868 KB Output is correct
7 Correct 6 ms 868 KB Output is correct
8 Correct 5 ms 868 KB Output is correct
9 Correct 7 ms 896 KB Output is correct
10 Correct 7 ms 996 KB Output is correct
11 Correct 17 ms 1872 KB Output is correct
12 Correct 18 ms 1872 KB Output is correct

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1872 KB Output is correct
2 Correct 31 ms 3036 KB Output is correct
3 Correct 37 ms 3148 KB Output is correct
4 Correct 195 ms 12900 KB Output is correct
5 Correct 208 ms 12900 KB Output is correct
6 Runtime error 358 ms 44232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -