oj.uz

답안 #409480

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
409480 2021-05-20T21:49:50 Z AugustinasJucas Salesman (IOI09_salesman) C++14
100 / 100
 2864 ms 62360 KB 
#include <bits/stdc++.h>
using namespace std;
const long long inf = 2e9;
struct medis{
	struct node{
		int val[4] = {-inf, -inf, -inf, -inf};
		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]);
		}
	}
	long long get(int v, int l, int r, int ii){
		if(l <= mas[v].l && mas[v].r <= r){
			return mas[v].val[ii];
		}else if(r < mas[v].l || mas[v].r < l){
			return -inf;
		}else{
			return max(get(v*2, l, r, ii), get(v*2+1, l, r, ii));
		}
	}
};
 
int n, U, D, s;
const int dydis = 5e5 + 10;
vector<pair<int, int> > fairs[dydis];
long long curAns[dydis];
long long pref[dydis] = {};
medis v(dydis);
void updateCur(int ind, long long x){
	curAns[ind] = x;
	v.change(1, ind, ind, curAns[ind] + 1ll * D * ind, 0);
	v.change(1, ind, ind, curAns[ind] - 1ll * U * ind, 1);
}	
long long fMx1(int l, int r){
	return v.get(1, l, r, 0);
}
long long fMx2(int l, int r){
	return v.get(1, l, r, 1);
}
long long fMx3(int l, int r){
	return v.get(1, l, r, 2);
}
void upd1(int d){
	if(fairs[d].size() == 0) return;
	vector<pair<int, long long> > chang;
	for(auto x : fairs[d]){
		long long galiBut = fMx1(0, x.first-1) - 1ll * x.first * D; 
		chang.push_back({x.first,  galiBut + x.second});
	}
	for(int i = (int)fairs[d].size()-1; i > -1; i--){
		auto x = fairs[d][i];
		long long galiBut = fMx2(x.first+1, dydis-1) + 1ll * x.first * U;
		chang.push_back({x.first, galiBut + x.second});
	}
	for(auto x : chang){
		int ind = x.first;
		long long val = x.second;
		if(val < curAns[ind]){
			continue;
		}
		updateCur(ind, val);
	}
}
void upd2(int d){
	if(fairs[d].size() <= 1) return ;
	long long sm = 0;
	//UX + [DA - pref[A] + curVal[A]] + [pref[B]-B(D+U)]
	for(auto x : fairs[d]){
		sm += x.second;
		pref[x.first] = sm;
		v.change(1, x.first, x.first, 1ll * D * x.first - pref[x.first] + curAns[x.first], 2); // Kaip A
		v.change(1, x.first, x.first, 1ll * pref[x.first] - x.first * (D+U), 3); // kaip B
	}
	vector<pair<int, long long> > chang;
	for(int i = 1; i < (int)fairs[d].size(); i++){
		auto x = fairs[d][i];
		long long kair = v.get(1, 0, x.first-1, 2);
		long long desn = v.get(1, x.first, dydis-1, 3);
		chang.push_back({x.first, kair+desn + U * x.first});
	}
	pair<int, int> last = {-1, -1};
	//-XD + [curVal[A] + pref[A-1] - AU] + [B(D+U)-pref[B]]
	for(auto x : fairs[d]){
		if(last.first != -1)
			v.change(1, x.first, x.first, curAns[x.first] + (last.first == -1 ? 0 : pref[last.first]) -1ll * U * x.first, 2); // Kaip A
		v.change(1, x.first, x.first, x.first*(D+U) - (last.first == -1 ? 0 : pref[last.first]), 3); // kaip B
		last = x;
	}
	for(int i = 0; i < (int)fairs[d].size()-1; i++){
		auto x = fairs[d][i];
		long long kair = v.get(1, 0, x.first, 3);
		long long desn = v.get(1, x.first+1, dydis-1, 2);
		chang.push_back({x.first, kair+desn - D * x.first});
	}
	for(auto x : chang){
		int ind = x.first;
		long long val = x.second;
		if(val < curAns[ind]){
			continue;
		}
		updateCur(ind, val);
	}
	for(auto x : fairs[d]){
		v.change(1, x.first, x.first, -inf, 2); // kaip B
		v.change(1, x.first, x.first, -inf, 3);
	}
	//cout << v.get(1, 0, dydis-1, 2) << " " << v.get(1, 0, dydis-1, 3) << endl;
/*


X       X      X X   X    X    X
A              ^          B
 
-(X-A)*D - (B-X)*(D+U) + pref[B] - pref[A] + curVal[A]
DA - BD - BU + UX + pref[B] - pref[A] + curVal[A]
UX + [DA - pref[A] + curVal[A]] + [pref[B]-B(D+U)]



X       X      X X   X    X    X
B                ^        A
 
-(A-X)*U - (X-B)*(D+U) + pref[A-1] - pref[B] + curVal[A]
-AU - XD + BD + BU + pref[A-1] - pref[B] + curVal[A]
-XD + [curVal[A] + pref[A-1] - AU] + [B(D+U)-pref[B]]
 
 
*/
 
}
 
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++){
		if(fairs[i].size() == 0) continue;
 
//        cout << i << " diena: \n";
		upd1(i);
//        cout << "po paprasto: ";
//		for(int i = 0; i <= 5; i++) cout << (curAns[i] == -inf ? -69 : curAns[i]) << " ";
//        cout << endl;
		upd2(i);
//        cout << "po antrojo: "; for(int i = 0; i <= 5; i++) cout << (curAns[i] == -inf ? -69 : curAns[i]) << " ";
//        cout << endl;
//        cout << endl;
 
	}
	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;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 39356 KB Output is correct
2 Correct 27 ms 39344 KB Output is correct
3 Correct 28 ms 39352 KB Output is correct
4 Correct 31 ms 39500 KB Output is correct
5 Correct 38 ms 39504 KB Output is correct
6 Correct 82 ms 39972 KB Output is correct
7 Correct 141 ms 40920 KB Output is correct
8 Correct 259 ms 44248 KB Output is correct
9 Correct 344 ms 46432 KB Output is correct
10 Correct 526 ms 53532 KB Output is correct
11 Correct 753 ms 54208 KB Output is correct
12 Correct 957 ms 57960 KB Output is correct
13 Correct 1057 ms 58464 KB Output is correct
14 Correct 1253 ms 61764 KB Output is correct
15 Correct 987 ms 61740 KB Output is correct
16 Correct 1112 ms 61784 KB Output is correct
17 Correct 28 ms 39500 KB Output is correct
18 Correct 32 ms 39368 KB Output is correct
19 Correct 32 ms 39496 KB Output is correct
20 Correct 38 ms 39500 KB Output is correct
21 Correct 37 ms 39516 KB Output is correct
22 Correct 47 ms 39540 KB Output is correct
23 Correct 47 ms 39628 KB Output is correct
24 Correct 45 ms 39620 KB Output is correct
25 Correct 598 ms 46220 KB Output is correct
26 Correct 982 ms 50164 KB Output is correct
27 Correct 1803 ms 57400 KB Output is correct
28 Correct 1721 ms 54860 KB Output is correct
29 Correct 2864 ms 55156 KB Output is correct
30 Correct 2612 ms 62360 KB Output is correct