제출 #953682

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
953682		lovrot	Bitaro's travel (JOI23_travel)	C++17	100 / 100	205 ms	38532 KiB

travel

#include <cstdio> 
#include <vector> 

#define PB push_back

using namespace std; 

typedef long long ll;

const int LOG = 35;
const int N = 2e5 + 10;

int n;
ll X[N]; 

vector<int> L[N], R[N]; 

ll solve(int l, int r, bool flag) {
	if(l == 0 && r == n - 1) return 0;
	ll ret = 0; 
	
//	printf("%d %d %d \n", l, r, flag);

	if(flag == 0) {
		if(r == n - 1) return X[l] - X[0];
		if(l == 0) return X[r + 1] - X[0] + solve(0, r + 1, 1);

		int nxt = -1;
		for(int i = (int) L[r + 1].size() - 1; i >= 0; --i)
			if(L[r + 1][i] < l) {
				nxt = L[r + 1][i];
				break;
			}
		return nxt == -1 ? X[l] - X[0] + solve(0, r, 0) : X[l] + X[r + 1] - 2 * X[nxt + 1] + solve(nxt + 1, r + 1, 1);
	} else {
		if(l == 0) return X[n - 1] - X[r]; 
		if(r == n - 1) return X[n - 1] - X[l - 1] + solve(l - 1, n - 1, 0);

		int nxt = -1;
		for(int i = (int) R[l - 1].size() - 1; i >= 0; --i)
			if(R[l - 1][i] > r) {
				nxt = R[l - 1][i];
				break;
			}
		return nxt == -1 ? X[n - 1] - X[r] + solve(l, n - 1, 1) : 2 * X[nxt - 1] - X[r] - X[l - 1] + solve(l - 1, nxt - 1, 0);
	}
	return 0;
}

int main() {
	scanf("%d", &n);

	for(int i = 0; i < n; ++i) {
		scanf("%lld", X + i); 

		if(i) {
			for(int x : L[i - 1])
				if(X[x + 1] - X[x] > X[i] - X[x + 1]) L[i].PB(x);
			L[i].PB(i - 1);
		}
	}

	for(int i = n - 2; i >= 0; --i) {
		for(int x : R[i + 1])
			if(X[x] - X[x - 1] >= X[x - 1] - X[i]) R[i].PB(x); 
		R[i].PB(i + 1);
	}

	int q; scanf("%d", &q);
	for(; q--; ) {
		ll x; scanf("%lld", &x); 

		int lo = -1, hi = n;
		for(; hi - lo > 1; ) {
			int mi = (lo + hi) / 2;
			if(X[mi] <= x) lo = mi;
			else hi = mi;
		}
	
//		printf("%d %d\n", lo, hi);
		if(lo == -1) printf("%lld\n", X[0] - x + solve(0, 0, 1));
		else if(hi == n) printf("%lld\n", x - X[n - 1] + solve(n - 1, n - 1, 0));
		else printf("%lld\n", X[hi] - x >= x - X[lo] ? solve(lo, lo, 0) + x - X[lo] : solve(hi, hi, 1) + X[hi] - x);
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

travel.cpp: In function 'll solve(int, int, bool)':
travel.cpp:20:5: warning: unused variable 'ret' [-Wunused-variable]
   20 |  ll ret = 0;
      |     ^~~
travel.cpp: In function 'int main()':
travel.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
travel.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   scanf("%lld", X + i);
      |   ~~~~~^~~~~~~~~~~~~~~
travel.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
travel.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   ll x; scanf("%lld", &x);
      |         ~~~~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 55 / 55