oj.uz

Submission #796231

# Submission time Handle Problem Language Result Execution time Memory
796231 2023-07-28T08:14:24 Z 박상훈(#10069) Security Guard (JOI23_guard) C++17
0 / 100
 1 ms 212 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;

	if (n > 1) treeR.init(1, 1, n-1);
	if (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);

		if (n==1){
			printf("%lld\n", abs(x - X[1]));
			continue;
		}

		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

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

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -