oj.uz

Submission #68465

# Submission time Handle Problem Language Result Execution time Memory
68465 2018-08-17T07:48:35 Z quoriess Divide and conquer (IZhO14_divide) C++14
52 / 100
 374 ms 22728 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 int MAXN=1e5+5;
lli segmentTree[4*MAXN];
/*
8 10
7 3 5 12 2 7 3 4
 * */
void buildTree(int node,int a,int 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(int node,int a,int 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]);
	}
}
int queryTree(int node,int a,int b,int l,int r){
	if(a>b||a>r||b<l)return 1e7;
	if(a>=l&&b<=r)return segmentTree[node];
	int q1=queryTree(node*2,a,(a+b)/2,l,r);
	int q2=queryTree(node*2+1,(a+b)/2+1,b,l,r);
	return min(q1,q2);
}
vector<data> datas;
int main(){
	int n;
	cin>>n;
	for (int i = 0; i < n; i++)
	{
		int 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 (int 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 (int 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());
	int sr=0;
	map<lli,int> 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);
	int dp[n];
	dp[0]=goldpre[0];
	for (int i = 1; i < n; i++)
	{
		int 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 (int 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 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 2 ms 580 KB Output is correct
7 Correct 2 ms 580 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Incorrect 3 ms 724 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Incorrect 3 ms 748 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 14 ms 1704 KB Output is correct
2 Correct 23 ms 2788 KB Output is correct
3 Correct 32 ms 2788 KB Output is correct
4 Correct 156 ms 11564 KB Output is correct
5 Correct 199 ms 11604 KB Output is correct
6 Correct 374 ms 22660 KB Output is correct
7 Correct 361 ms 22692 KB Output is correct
8 Correct 307 ms 22728 KB Output is correct
9 Correct 291 ms 22728 KB Output is correct
10 Correct 313 ms 22728 KB Output is correct
11 Correct 336 ms 22728 KB Output is correct
12 Correct 322 ms 22728 KB Output is correct