oj.uz

Submission #394004

# Submission time Handle Problem Language Result Execution time Memory
394004 2021-04-25T07:41:04 Z Berted Salesman (IOI09_salesman) C++14
100 / 100
 822 ms 43460 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 27724 KB Output is correct
2 Correct 19 ms 27732 KB Output is correct
3 Correct 18 ms 27724 KB Output is correct
4 Correct 21 ms 27820 KB Output is correct
5 Correct 23 ms 27940 KB Output is correct
6 Correct 51 ms 28452 KB Output is correct
7 Correct 104 ms 29380 KB Output is correct
8 Correct 197 ms 30960 KB Output is correct
9 Correct 237 ms 32528 KB Output is correct
10 Correct 385 ms 37312 KB Output is correct
11 Correct 564 ms 37188 KB Output is correct
12 Correct 656 ms 40356 KB Output is correct
13 Correct 667 ms 40352 KB Output is correct
14 Correct 818 ms 43372 KB Output is correct
15 Correct 638 ms 43460 KB Output is correct
16 Correct 822 ms 43428 KB Output is correct
17 Correct 18 ms 27720 KB Output is correct
18 Correct 19 ms 27684 KB Output is correct
19 Correct 21 ms 27700 KB Output is correct
20 Correct 20 ms 27696 KB Output is correct
21 Correct 21 ms 27752 KB Output is correct
22 Correct 23 ms 27764 KB Output is correct
23 Correct 22 ms 27824 KB Output is correct
24 Correct 22 ms 27852 KB Output is correct
25 Correct 170 ms 29100 KB Output is correct
26 Correct 275 ms 31040 KB Output is correct
27 Correct 465 ms 34100 KB Output is correct
28 Correct 492 ms 32956 KB Output is correct
29 Correct 755 ms 33092 KB Output is correct
30 Correct 707 ms 35984 KB Output is correct