oj.uz

Submission #796187

# Submission time Handle Problem Language Result Execution time Memory
796187 2023-07-28T07:37:24 Z 박상훈(#10069) Bitaro's travel (JOI23_travel) C++17
0 / 100
 676 ms 1048580 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

constexpr ll INF = 2e18;

ll X[200200];

struct Seg1{
	ll tree[800800];

	void init(int i, int l, int r){
		if (l==r){
			tree[i] = X[l+1] - X[l] * 2;
			return;
		}

		int m = (l+r)>>1;
		init(i<<1, l, m); init(i<<1|1, m+1, r);
		tree[i] = max(tree[i<<1], tree[i<<1|1]);
	}

	int prf(int i, int l, int r, int s, ll x){
		if (r<s) return -1;
		if (tree[i] < x) return -1;
		if (l==r) return l;

		int m = (l+r)>>1;
		
		int ret = prf(i<<1, l, m, s, x);
		if (ret!=-1) return ret;

		return prf(i<<1|1, m+1, r, s, x);
	}
}treeR;

struct Seg2{
	ll tree[800800];

	void init(int i, int l, int r){
		if (l==r){
			tree[i] = X[l] * 2 - X[l-1];
			return;
		}

		int m = (l+r)>>1;
		init(i<<1, l, m); init(i<<1|1, m+1, r);
		tree[i] = max(tree[i<<1], tree[i<<1|1]);
	}

	int suf(int i, int l, int r, int e, ll x){
		if (e<l) return -1;
		if (tree[i] < x) return -1;
		if (l==r) return l;

		int m = (l+r)>>1;
		
		int ret = suf(i<<1|1, m+1, r, e, x);
		if (ret!=-1) return ret;

		return suf(i<<1, l, m, e, x);
	}
}treeL;

ll ans, cnt;
int n;

int goRight(ll x, ll p, int i){
	int ret = treeR.prf(1, 1, n-1, i, -p);
	if (ret==-1){
		ret = n;
		cnt++;
	}

	ans += X[ret] - x;

	// printf(" go right %lld %lld %d -> %lld\n", x, p, i, X[ret]);
	return ret;
}

int goLeft(ll x, ll q, int j){
	int ret = treeL.suf(1, 2, n, j, q+1);
	if (ret==-1){
		ret = 1;
		cnt++;
	}

	ans += x - X[ret];

	// printf(" go left %lld %lld %d -> %lld\n", x, q, j, X[ret]);
	return ret;
}

int main(){
	scanf("%d", &n);
	for (int i=1;i<=n;i++) scanf("%lld", X+i);
	X[0] = -INF;
	X[n+1] = INF;

	treeR.init(1, 1, n-1);
	treeL.init(1, 2, n);

	multiset<pair<ll, int>> st;
	for (int i=1;i<=n;i++) st.emplace(X[i], i);

	int q;
	scanf("%d", &q);
	while(q--){
		ll x;
		int idx = -1;
		scanf("%lld", &x);

		ans = 0;
		cnt = 0;

		auto iter = st.lower_bound(pair<ll, int>(x, -1));
		if (iter==st.end()){
			printf("%lld\n", x - X[1]);
			continue;
		}

		if (iter==st.begin()){
			printf("%lld\n", X[n] - x);
			continue;
		}

		if (abs((prev(iter)->first)-x) <= abs((iter->first)-x)){
			idx = goLeft(x, iter->first, prev(iter)->second);
		}

		while(true){
			ll cur = (idx==-1)?x:X[idx];
			ll lim = (idx==-1)?(prev(iter)->first):X[idx-1];
			int fuck = (idx==-1)?(iter->second):(idx+1);

			idx = goRight(cur, lim, fuck);
			if (cnt==2) break;

			cur = X[idx];
			lim = X[idx+1];
			fuck = idx-1;

			idx = goLeft(cur, lim, fuck);
			if (cnt==2) break;
		}

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

Compilation message

travel.cpp: In function 'int main()':
travel.cpp:96:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
travel.cpp:97:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |  for (int i=1;i<=n;i++) scanf("%lld", X+i);
      |                         ~~~~~^~~~~~~~~~~~~
travel.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
travel.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   scanf("%lld", &x);
      |   ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 540 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Runtime error 676 ms 1048580 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 540 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Runtime error 676 ms 1048580 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Runtime error 361 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 540 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Runtime error 676 ms 1048580 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -