[Blog] [Docs] [Code] [Slides] [About]

KickStart 2020 Round D-D Locked Doors

2020-07-15 20:32 CST

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

class Node {
public:
int l, r;
int val;
};

int n = 0, q = 0;
int d[100005] = {};
Node t[400020] = {};

void build(int cur, int l, int r) {
t[cur].l = l;
t[cur].r = r;
if (l == r) {
t[cur].val = d[l];
return;
}
int m = (l + r) / 2;
build(cur << 1, l, m);
build(cur << 1 | 1, m + 1, r);
t[cur].val = max(t[cur << 1].val, t[cur << 1 | 1].val);
}

int query(int cur, int l, int r) {
if (t[cur].l == l && t[cur].r == r) {
return t[cur].val;
}
if (t[cur << 1].r >= r) {
return query(cur << 1, l, r);
} else if (t[cur << 1 | 1].l <= l) {
return query(cur << 1 | 1, l, r);
} else {
return max(query(cur << 1, l, t[cur << 1].r),
query(cur << 1 | 1, t[cur << 1 | 1].l, r));
}
}

bool check(int s, int k, int step) {
// go left 'step' steps ok?
int farL = s - step, farR = s + (k - step);
int maxL = query(1, farL, s - 1);
int maxR = query(1, s, farR);
return maxL < maxR;
}

int solve(int s, int k) {
int step = 0, l = max(1, k - (n - s)), r = min(s - 1, k);
while (l <= r) {
int mid = (l + r) / 2;
if (check(s, k, mid)) {
step = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
int ansL = s - step - 1;
int ansR = s + (k - step) + 1;
return d[ansL] < d[ansR - 1] ? ansL : ansR;
}

int main() {
int T = 0;
scanf("%d", &T);
for (int t = 1; t <= T; ++t) {
scanf("%d %d", &n, &q);
d[0] = d[n] = 0x3f3f3f3f;
for (int i = 1; i < n; ++i) {
scanf("%d", d + i);
}
build(1, 0, n);
printf("Case #%d: ", t);
for (int i = 1; i <= q; ++i) {
int s = 0, k = 0;
scanf("%d %d", &s, &k);
printf("%d ", k == 1 ? s : solve(s, k - 2));
}
printf("\n");
}
return 0;
}

<EOF>