Submission #1140942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140942		sano	Salesman (IOI09_salesman)	C++20	100 / 100	714 ms	46340 KiB

salesman

#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#define shit short int
#define ll long long
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define NEK 2047483648
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define sig 0.0000001

using namespace std;

struct to {
	int t, a, w, ind;
};

bool zorad(to a, to b) {
	return a.a < b.a;
}

bool zorad2(to a, to b) {
	if (a.t == b.t) {
		return a.a < b.a;
	}
	return a.t < b.t;
}

class intervalac {
	int n;
	vec<int> l, r, in;
	void update(int s) {
		in[s] = max(in[s * 2], in[s * 2 + 1]);
		return;
	}
public:
	intervalac(int vel) {
		n = 1;
		while (n < vel) n *= 2;
		l.resize(2 * n); r.resize(2 * n); in.resize(2 * n);
		For(i, n) {
			l[i + n] = i;
			r[i + n] = i;
			in[i + n] = (-1) * NEK;
		}
		rffor(i, 1, (n - 1)) {
			l[i] = l[i * 2];
			r[i] = r[i * 2 + 1];
			update(i);
		}
		return;
	}
	int daj(int a, int b, int s = 1) {
		if (l[s] > b || r[s] < a) return (-1) * NEK;
		if (a <= l[s] && r[s] <= b) return in[s];
		return max(daj(a, b, s * 2), daj(a, b, s * 2 + 1));
	}
	void zmen(int a, int k) {
		a += n;
		in[a] = k;
		a /= 2;
		while (a) {
			update(a);
			a /= 2;
		}
		return;
	}
};

void solve() {
	int n, u, d, s; cin >> n >> u >> d >> s;
	to p[500001], p2[500001];
	For(i, n) {
		int t, a, w; cin >> t >> a >> w;
		p[i] = { t, a, w, i };
		p2[i] = { t, a, w, i };
	}
	p[n] = { NEK, s, 0, n };
	sort(p, p + n + 1, zorad);
	vec<int> i_p(n + 1, -1);
	For(i, n+1) {
		i_p[p[i].ind] = i;
	}
	sort(p2, p2 + n, zorad2);
	intervalac seg1(n+1), seg2(n+1);
	seg1.zmen(i_p[n], d* s);
	seg2.zmen(i_p[n], (-1) * u * s);
	int cas = -1;
	int suc = 0;
	priority_queue<pii> se1, se2;
	vec<to> rovnake;
	vec<int> psuc;
	For(i, n) {
		if (p2[i].t != cas) {
			int maxi = (-1) * NEK;
			vec<int> vys(rovnake.size());
			For(j, rovnake.size()) {
				while (true) {
					if (se1.top().ss >= j) break;
					se1.pop();
				}
				maxi = max(maxi, (u + d) * rovnake[j].a - psuc[j]);
				vys[j] = maxi + se1.top().ff - d * rovnake[j].a;
			}
			maxi = (-1) * NEK;
			rfor(j, rovnake.size() - 1) {
				while (true) {
					if (se2.top().ss <= j) break;
					se2.pop();
				}
				maxi = max(maxi, psuc[j] + rovnake[j].w - (u + d) * rovnake[j].a);
				vys[j] = max(vys[j], maxi + se2.top().ff + u * rovnake[j].a);
			}
			For(j, vys.size()) {
				seg1.zmen(i_p[rovnake[j].ind], vys[j] + d * rovnake[j].a);
				seg2.zmen(i_p[rovnake[j].ind], vys[j] - u * rovnake[j].a);
			}
			cas = p2[i].t;
			suc = 0;
			rovnake.clear();
			psuc.clear();
			while (!se1.empty()) se1.pop();
			while (!se2.empty()) se2.pop();
		}
		int o1 = seg1.daj(0, i_p[p2[i].ind]) - d * p2[i].a;
		int o2 = seg2.daj(i_p[p2[i].ind], n + 1 - 1) + u * p2[i].a;
		int o = max(o1, o2);
		se1.push({ suc - u * p2[i].a + p2[i].w + o, rovnake.size() });
		se2.push({ (o + d * p2[i].a - suc), rovnake.size() });
		psuc.push_back(suc);
		suc += p2[i].w;
		rovnake.push_back(p2[i]);
	}

	int maxi = (-1) * NEK;
	vec<int> vys(rovnake.size());
	For(j, rovnake.size()) {
		while (true) {
			if (se1.top().ss >= j) break;
			se1.pop();
		}
		maxi = max(maxi, ((u + d) * rovnake[j].a - psuc[j]));
		vys[j] = maxi + se1.top().ff - d * rovnake[j].a;
	}
	maxi = (-1) * NEK;
	rfor(j, rovnake.size() - 1) {
		while (true) {
			if (se2.top().ss <= j) break;
			se2.pop();
		}
		maxi = max(maxi, psuc[j] + rovnake[j].w - (u + d) * rovnake[j].a);
		vys[j] = max(vys[j], maxi + se2.top().ff + u * rovnake[j].a);
	}
	For(j, vys.size()) {
		seg1.zmen(i_p[rovnake[j].ind], vys[j] + d * rovnake[j].a);
		seg2.zmen(i_p[rovnake[j].ind], vys[j] - u * rovnake[j].a);
	}
	int o1 = seg1.daj(0, i_p[n]) - d * s;
	int o2 = seg2.daj(i_p[n], n + 1 - 1) + u * s;
	cout << max(o1, o2) << '\n';
	return;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	//cin >> t;
	t = 1;
	while (t--) {
		solve();
	}
	return 0;
}

• Subtask 1: 100 / 100