Submission #549018

#	Time	Username	Problem	Language	Result	Execution time	Memory
549018		LucaDantas	Railway Trip (JOI17_railway_trip)	C++17	0 / 100	2076 ms	8020 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 1e5+10;

int a[maxn], l[maxn][2], r[maxn][2];

// l[] e r[] salvam tanto o primeiro elemento maior como a distância

vector<int> pos[21];

int dist(int x, int y, int k) {
	// se x==y ele retorna -1 e é pra retornar isso mesmo
	if(x > y) swap(x, y);
	return lower_bound(pos[k].begin(), pos[k].end(), y) - lower_bound(pos[k].begin(), pos[k].end(), x) - 1;
}

int main() {
	int n, k, q; scanf("%d %d %d", &n, &k, &q);
	for(int i = 0; i < n; i++) {
		scanf("%d", a+i);
		for(int j = 0; j <= a[i]; j++)
			pos[j].push_back(i);
	}

	for(int i = 0; i < n; i++) {
		if(a[i] == k) { l[i][0] = i; l[i][1] = 0; continue; }
		l[i][0] = i-1; l[i][1] = 1;
		while(a[l[i][0]] <= a[i]) {
			l[i][1] = (a[l[i][0]] == a[i] ? l[l[i][0]][1] : 0) + 1;
			l[i][0] = l[l[i][0]][0];
		}
	}
	
	for(int i = n-1; i >= 0; i--) {
		if(a[i] == k) { r[i][0] = i, r[i][1] = 0; continue; }
		r[i][0] = i+1; r[i][1] = 1;
		while(a[r[i][0]] <= a[i]) {
			r[i][1] = (a[r[i][0]] == a[i] ? r[r[i][0]][1] : 0) + 1;
			r[i][0] = r[r[i][0]][0];
		}
	}

	while(q--) {
		int x, y; scanf("%d %d", &x, &y);
		--x, --y;
		pair<int,int> L[2], R[2]; // pair(elemento, distancia)
		L[0] = R[0] = {x, 0}; L[1] = R[1] = {y, 0};

		int ans = 0x3f3f3f3f;

		auto upd = [&](int k) {
			L[k].second += l[L[k].first][1];
			L[k].first = l[L[k].first][0];

			R[k].second += r[R[k].first][1];
			R[k].first = r[R[k].first][0];

			R[k].second = min(R[k].second, L[k].second+1);
			L[k].second = min(L[k].second, R[k].second+1);
		};

		auto get_ans = [&]() {
			ans = min(ans, L[0].second + L[1].second + dist(L[0].first, L[1].first, min(a[L[0].first], a[L[1].first])));
			ans = min(ans, R[0].second + L[1].second + dist(R[0].first, L[1].first, min(a[R[0].first], a[L[1].first])));
			ans = min(ans, L[0].second + R[1].second + dist(L[0].first, R[1].first, min(a[L[0].first], a[R[1].first])));
			ans = min(ans, R[0].second + R[1].second + dist(R[0].first, R[1].first, min(a[R[0].first], a[R[1].first])));
		};

		L[0] = R[0] = {x, 0};
		for(int i = 0; i < k; i++) {
			L[1] = R[1] = {y, 0};
			for(int j = 0; j < k; j++) {
				get_ans();
				upd(1);
			}
			upd(0);
		}

		printf("%d\n", ans);
	}
}

Compilation message (stderr)

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:19:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  int n, k, q; scanf("%d %d %d", &n, &k, &q);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   scanf("%d", a+i);
      |   ~~~~~^~~~~~~~~~~
railway_trip.cpp:45:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   int x, y; scanf("%d %d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55