Submission #408885

#	Time	Username	Problem	Language	Result	Execution time	Memory
408885		AugustinasJucas	Salesman (IOI09_salesman)	C++14	60 / 100	2811 ms	53140 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
const long  inf = 2e9;
const int dydis = 5e5 + 10;
struct medis{
	struct node{
		int val[4] = {(int)-2e9, (int)-2e9, (int)-2e9, (int)-2e9};
		int l, r;
	};
	vector<node> mas;
	int n;
	int dbInd = 0;
	void build(int v){
		if(v >= n){
			mas[v].l = mas[v].r = dbInd++;
		}else{
			build(v*2); build(v*2+1);
			mas[v].l = mas[v*2].l;
			mas[v].r = mas[v*2+1].r;
		}
	}
	medis(int dd){
		n = dd;
		mas.resize(2 * n + 1);
		build(1);
	}
	void change(int v, int l, int r, long long x, int ii){
		if(l <= mas[v].l && mas[v].r <= r){
			mas[v].val[ii] = x;
		}else if(r < mas[v].l || mas[v].r < l){
			return;
		}else{
			change(v*2, l, r, x, ii);
			change(v*2+1, l, r, x, ii);
			mas[v].val[ii] = max(mas[v*2].val[ii], mas[v*2+1].val[ii]);
		}
	}
	pair<long long, int> get(int v, int l, int r, int ii){
		if(l <= mas[v].l && mas[v].r <= r){
			return {mas[v].val[ii], mas[v].l};
		}else if(r < mas[v].l || mas[v].r < l){
			return {-inf, dydis-1};
		}else{
			return max(get(v*2, l, r, ii), get(v*2+1, l, r, ii));
		}
	}
};

int n, U, D, s;

vector<pair<int, int> > fairs[dydis];
int curAns[dydis];
medis v(dydis);
void updateCur(int ind, long long x){
	curAns[ind] = x;
	//[curAns[y]+u*y]
	//cout << ind << " -> " << x << endl;
	v.change(1, ind, ind, curAns[ind] + 1ll * D * ind, 0);
	v.change(1, ind, ind, curAns[ind] - 1ll * U * ind, 1);
	v.change(1, ind, ind, curAns[ind] + 1ll * D * ind, 2);
	v.change(1, ind, ind, curAns[ind] - 1ll * U * ind, 3) ; 
//	cout << "padarau " << ind << " i " << curAns[ind] <<" + " << D << " * " << ind << endl;
}	
pair<long long, int> fMx1(int l, int r){
	//cout << l << "; " << r << " maximumas, pirmame: " << v1.get(1, l, r) << endl;
	return v.get(1, l, r, 0);
}
pair<long long, int> fMx2(int l, int r){
	return v.get(1, l, r, 1);
}
pair<long long, int> fMx3(int l, int r){
	return v.get(1, l, r, 2);
}
pair<long long, int> fMx4(int l, int r){
	return v.get(1, l, r, 3);
}
void daryk(int d){
	
	if(fairs[d].size() == 0) return;
	int kurMax = -1;
	int lastFair = -1;
	long long pref = 0;
	vector<pair<int, long long> > chang;
	//cout << "darom " << d << "-aja diena!" << endl;
	for(auto x : fairs[d]){
		long long bv = (kurMax == -1 ? -inf : 1ll * curAns[kurMax] - 1ll * (x.first - kurMax) * D + pref); 
		long long galiBut = fMx1(lastFair+1, x.first-1).first - 1ll * x.first * D; 
	//	cout << x.first << " gali buti " << max(bv, galiBut) + x.second << endl;
		chang.push_back({x.first, max(bv, galiBut) + x.second});
		if(galiBut > bv){
			kurMax = fMx1(lastFair+1, x.first-1).second;
			pref = 0;
		}
		pref += x.second;
		lastFair = x.first;
	}
	//cout << "don " << endl;
	lastFair = dydis-1;
	kurMax = dydis-1;
	pref = 0;
	for(int i = (int)fairs[d].size()-1; i > -1; i--){
		auto x = fairs[d][i];
		long long bv = (kurMax == dydis-1 ? -inf : 1ll * curAns[kurMax] - 1ll * (kurMax - x.first) * U + pref);
		long long galiBut = fMx2(x.first+1, lastFair-1).first + 1ll * x.first * U;
		chang.push_back({x.first, max(bv, galiBut) + x.second});
		if(galiBut > bv){
			kurMax = fMx2(x.first+1, lastFair-1).second;
			pref = 0;
		}
		pref += x.second;
		lastFair = x.first;
		//cout << "kurMax = " << kurMax << endl;
	}
	 
	
	
	
	// f(x, z) = [yu + curSum[y]] minimumas intervale [x; z]
	//ux + [SM[x; z] - z(d+u)] + [yd + curSum[y]]   f, kai x konstanta - nemazejanti
	kurMax = dydis-1;
	lastFair = dydis-1;
	pref = fairs[d].back().second;
	//cout << "keliauti desinen (d) = " << D<< endl;
	for(int i = (int)fairs[d].size()-2; i > -1; i--){
		auto x = fairs[d][i];
		lastFair = fairs[d][i+1].first;
		long long bv = (kurMax == dydis-1 ? -inf : 1ll * x.first * U + pref - kurMax * (D + U) + fMx3(lastFair, kurMax).first); 
		long long galiBut = fairs[d][i+1].second + fMx3(x.first+1, lastFair-1).first + 1ll * x.first * U - 1ll * (D + U) * lastFair; 
	//	cout << "bv: " << bv << ", o gali buti: " <<  fairs[d][i+1].second  << " + " << fMx3(x.first+1, lastFair-1).first << " + " <<  1ll * x.first * U  <<"- " <<  (D + U) << " * "<< lastFair << endl;
		chang.push_back({x.first, max(bv, galiBut) + x.second});
		if(galiBut > bv){
			kurMax = lastFair;
			pref = 0;
		}
		pref += x.second;
	}
	

	kurMax = -1;
	lastFair = -1;
	pref = fairs[d][0].second;
	//-dx + z(u+d) + SM[z; x] + [curSum[y]- uy]
	for(int i = 1; i < (int)fairs[d].size(); i++){
		auto x = fairs[d][i];
		lastFair = fairs[d][i-1].first;
		long long bv = (kurMax == dydis-1 ? -inf : -1ll * x.first * D + pref + kurMax * (D + U) + fMx4(kurMax, lastFair).first); 
		long long galiBut = fairs[d][i-1].second + fMx4(lastFair+1, x.first-1).first - 1ll * x.first * D + 1ll * (D + U) * lastFair; 
		//cout << "bv: " << bv << ", o gali buti: " <<  fairs[d][i-1].second  << " + " << fMx4(lastFair+1, x.first-1).first << " - " <<  1ll * x.first * D  <<"+" <<  (D + U) << " * "<< lastFair << endl;
		chang.push_back({x.first, max(bv, galiBut) + x.second});
		if(galiBut > bv){
			kurMax = lastFair;
			pref = 0;
		}
		pref += x.second;
	}
	
	for(auto x : chang){
		int ind = x.first;
		long long val = x.second;
	//	cout << "norim " << ind << " pakeisti i " << val << endl;
		if(val < curAns[ind]){
			continue;
		}
		updateCur(ind, val);
	}
	//cout << "po " << d << " dienos, pirmi 10: ";
	//for(int i = 0; i <= 10; i++) cout << (curAns[i] == -inf ? -1 : curAns[i]) << " ";
	//cout << endl; 
}
int main(){
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	for(int i = 0; i < dydis; i++) curAns[i] = -inf;
	cin >> n >> U >> D >> s;
	
	updateCur(s, 0);
	for(int i = 0; i < n; i++){
		int t, l, p; cin >> t >> l >> p;
		fairs[t].push_back({l, p});
	}
	for(int i = 0; i < dydis; i++){
		sort(fairs[i].begin(), fairs[i].end());
	}
	for(int i = 0; i < dydis; i++){
		daryk(i);
	}
	long long ans = 0;
	for(int i = 0; i < dydis; i++){
		ans = max(ans, curAns[i] - 1ll * (i < s ? D : U) * abs(s-i));
	}
	cout << ans;
	return 0;
}
/*

4 1 1 1
2 2 
2 5 5
2 6 6

1 1 3
2 5 5

3 1 2 0
1 2 50
2 1 50
2 3 50

 50    50   50  0
-inf  50  -inf  S



    X [   Y    ^  ^    ^   ^]
    x     y                 z
    
    -(y-x)*u  - (z-y)*(d+u) + SM[x; z] + curSum[y]
	ux - zd - zu + yd
    ux - zd - zu + yd + SM[x; z] + curSum[y]
    
    ux + [SM[x; z] - z(d+u)] + [yd + curSum[y]] IR y < z
								f(x, z)
	
	dx -SM[0; x-1] + [SM[0; z] - z(d+u)] + f(x, z);  f, kai x konstanta - nemazejanti
    
    KAI PAKEICIU x-a:
    * arba z-a judinsiu i x vieta
    * arba z-o nejudinsiu!!
    
    
    
    [    ^   ^    ^ Y  ] X
	z               y    x
	
	-(x-y)*d - (y-z)*(d+u)SM[z; x] + curSum[y]
	-dx+dy - dy - uy + zd + zu + SM[z; x] + curSum[y]
	-dx + z(u+d) + SM[z; x] + [curSum[y]- uy]


4 1 3 5
1 1 3
1 2 3
1 10 100
1 10000 1

*/

• Subtask 1: 60 / 100