Submission #394004

#	Time	Username	Problem	Language	Result	Execution time	Memory
394004		Berted	Salesman (IOI09_salesman)	C++14	100 / 100	822 ms	43460 KiB

salesman

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
#define pii pair<int, int>
#define fst first
#define snd second
const ll INF = 1e15;
const int MX = 500001;

using namespace std;

int N, U, D, S;
vector<pii> A[MX + 1];
ll ans[MX + 1], BIT[2][MX + 1], rev[2][MX + 1];
vector<int> revI[2];

inline void init()
{
	for (int i = 0; i <= MX; i++) 
	{
		BIT[0][i] = BIT[1][i] = -INF;
		rev[0][i] = rev[1][i] = -INF - 1;
	}
}

inline void upd(int t, int i, ll val)
{
	for (; i <= MX; i += i & (-i)) 
	{
		if (val > BIT[t][i]) 
		{
			if (rev[t][i] == -INF - 1)
			{
				rev[t][i] = BIT[t][i];
				revI[t].push_back(i);
			}
			BIT[t][i] = val;
		}
	}
}

inline void revert(bool b)
{
	for (int k = 0; k < 2; k++)
	{
		for (const int &i : revI[k])
		{
			if (b) BIT[k][i] = rev[k][i];
			rev[k][i] = -INF - 1;
		}
		revI[k].clear();
	}
}

inline ll qry(int t, int i)
{
	ll ret = -INF;
	for(; i; i -= i & (-i)) {ret = max(ret, BIT[t][i]);}
	return ret;
}

inline ll getAns(int x)
{
	return max(qry(0, MX + 1 - x) + U * x, qry(1, x) - D * x);
}

inline void ins(int x, ll v)
{
	upd(0, MX + 1 - x, v - U * x);
	upd(1, x, v + D * x);
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> U >> D >> S;
	for (int i = 0; i < N; i++)
	{
		int T, L, M; cin >> T >> L >> M;
		A[T].push_back({L, M});
	}

	init(); ins(S, 0); revert(0);
	for (int i = 1; i <= MX; i++)
	{
		sort(A[i].begin(), A[i].end());
		for (int j = 0; j < A[i].size(); j++)
		{
			ll temp = getAns(A[i][j].fst) + A[i][j].snd;
			ins(A[i][j].fst, temp);
			ans[j] = temp;
		}
		revert(1);

		for (int j = A[i].size() - 1; j >= 0; j--)
		{
			ll temp = getAns(A[i][j].fst) + A[i][j].snd;
			ins(A[i][j].fst, temp);
			ans[j] = max(ans[j], temp);
		}
		revert(1);
		for (int j = 0; j < A[i].size(); j++) {ins(A[i][j].fst, ans[j]);}
		revert(0);
	}
	cout << getAns(S) << "\n";
	return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:88:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for (int j = 0; j < A[i].size(); j++)
      |                   ~~^~~~~~~~~~~~~
salesman.cpp:103:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   for (int j = 0; j < A[i].size(); j++) {ins(A[i][j].fst, ans[j]);}
      |                   ~~^~~~~~~~~~~~~

• Subtask 1: 100 / 100