| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 311611 | IgorI | 식물 비교 (IOI20_plants) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 500000;
const ll INF = 1e18;
int c;
int n;
int H[N];
int k;
pair<ll, int> tree[4 * N];
ll push[4 * N];
pair<ll, int> Merge(pair<ll, int> a, pair<ll, int> b)
{
return min(a, b);
}
void Push(int V)
{
tree[2 * V + 1].first += push[V];
tree[2 * V + 2].first += push[V];
push[2 * V + 1] += push[V];
push[2 * V + 2] += push[V];
push[V] = 0;
}
void Build(int L, int R, int V, vector<int> &r)
{
if (L + 1 == R)
{
tree[V] = {r[L], L};
return;
}
int M = (L + R) / 2;
Build(L, M, 2 * V + 1, r);
Build(M, R, 2 * V + 2, r);
tree[V] = Merge(tree[2 * V + 1], tree[2 * V + 2]);
}
pair<ll, int> Get(int l, int r, int L = 0, int R = n, int V = 0)
{
if (r <= L || R <= l) return {INF, 0};
if (l <= L && R <= r) return tree[V];
int M = (L + R) / 2;
Push(V);
return Merge(Get(l, r, L, M, 2 * V + 1), Get(l, r, M, R, 2 * V + 2));
}
void Add(int l, int r, ll x, int L = 0, int R = n, int V = 0)
{
if (r <= L || R <= l) return;
if (l <= L && R <= r)
{
tree[V].first += x;
push[V] += x;
return;
}
int M = (L + R) / 2;
Push(V);
Add(l, r, x, L, M, 2 * V + 1);
Add(l, r, x, M, R, 2 * V + 2);
tree[V] = Merge(tree[2 * V + 1], tree[2 * V + 2]);
}
int CGet(int l, int r)
{
if (l < 0)
{
l += n;
pair<ll, int> a = Get(l, n);
pair<ll, int> b = Get(0, r);
if (a.first == 0) return a.second;
if (b.first == 0) return b.second;
return -1;
}
pair<ll, int> a = Get(l, r);
if (a.first == 0) return a.second;
return -1;
}
void CAdd(int l, int r, ll x)
{
if (l < 0)
{
l += n;
Add(l, n, x);
Add(0, r, x);
}
else
{
Add(l, r, x);
}
}
pair<ll, int> tree2[4 * N];
void Build2(int L = 0, int R = n, int V = 0)
{
tree2[V] = {INF, L};
if (L + 1 == R) return;
int M = (L + R) / 2;
Build2(L, M, 2 * V + 1);
Build2(M, R, 2 * V + 2);
}
void Set2(int pos, int x, int L = 0, int R = n, int V = 0)
{
if (L + 1 == R)
{
tree2[V] = {x, L};
return;
}
int M = (L + R) / 2;
if (pos < M) Set2(pos, x, L, M, 2 * V + 1);
else Set2(pos, x, M, R, 2 * V + 2);
tree2[V] = min(tree2[2 * V + 1], tree2[2 * V + 2]);
}
pair<ll, int> Get2(int l, int r, int L = 0, int R = n, int V = 0)
{
if (r <= L || R <= l) return {INF, 0};
if (l <= L && R <= r) return tree2[V];
int M = (L + R) / 2;
return min(Get2(l, r, L, M, 2 * V + 1), Get2(l, r, M, R, 2 * V + 2));
}
int up_left[N], up_right[N];
int CGet2(int l, int r)
{
l = (l % n + n) % n;
r = (r % n + n) % n;
if (l > r)
{
if (l < 0) l += n;
if (r > n) r -= n;
pair<ll, int> a = Get2(l, n);
pair<ll, int> b = Get2(0, r);
if (a.first < INF) return a.second;
if (b.first < INF) return b.second;
return -1;
}
pair<ll, int> a = Get2(l, r);
if (a.first < INF) return a.second;
return -1;
}
void call(int i, int k, vector<int> &r, vector<int> &h1)
{
int id = CGet(i - k + 1, i);
while (id != -1)
{
call(id, k, r, h1);
id = CGet(i - k + 1, i);
}
up_right[i] = CGet2(i + 1, i + k);
up_left[i] = CGet2(i - k + 1, i);
h1[i] = c--;
Set2(i, h1[i]);
CAdd(i - k + 1, i, -1);
CAdd(i, i + 1, INF);
}
const int LG = 20;
ll le[LG][N], ri[LG][N];
void init(int K, vector<int> r)
{
k = K;
n = r.size();
vector<int> h1(n);
c = n;
Build(0, n, 0, r);
Build2();
int id = CGet(0, n);
while (id != -1)
{
call(id, k, r, h1);
id = CGet(0, n);
}
for (int i = 0; i < n; i++)
{
H[i] = h1[i];
}
for (int i = 0; i < n; i++)
{
{
ll ex = INF, pos = -1;
for (int j = i - k + 1; j < i; j++)
{
int id = (j % n + n) % n;
if (H[id] > H[i] && H[id] < ex)
{
ex = H[id];
pos = id;
}
}
le[0][i] = pos;
}
{
ll ex = INF, pos = -1;
for (int j = i + 1; j < i + k; j++)
{
int id = j % n;
if (H[id] > H[i] && H[id] < ex)
{
ex = H[id];
pos = id;
}
}
ri[0][i] = pos;
}
assert(le[0][i] == up_left[i]);
assert(ri[0][i] == up_right[i]);
}
for (int i = 0; 0 && i < n; i++)
{
if (up_left[i] != -1)
{
le[0][i] = i - up_left[i];
if (le[0][i] < 0) le[0][i] += n;
} else le[0][i] = INF;
if (up_right[i] != -1)
{
ri[0][i] = up_right[i] - i;
if (ri[0][i] < 0) ri[0][i] += n;
} else ri[0][i] = INF;
assert(le[0][i] < k || le[0][i] == INF);
assert(ri[0][i] < k || ri[0][i] == INF);
}
for (int j = 1; j < LG; j++)
{
for (int i = 0; i < n; i++)
{
if (le[j - 1][i] < INF)
le[j][i] = min(le[j - 1][i] + le[j - 1][((i - le[j - 1][i]) % n + n) % n], INF);
else
le[j][i] = INF;
if (ri[j - 1][i] < INF)
ri[j][i] = min(ri[j - 1][i] + ri[j - 1][(i + ri[j - 1][i]) % n], INF);
else
ri[j][i] = INF;
}
}
}
int Dist(int x, int y)
{
if (x < y) return min(y - x, n - y + x);
return min(x - y, n - x + y);
}
int compare_plants(int x, int y)
{
if (Dist(x, y) < k)
{
if (H[x] <= H[y]) return -1;
return 1;
}
ll d;
d = x;
while (Dist(d, y) >= k)
{
if (ri[0][d] == -1) break;
d = ri[0][d];
}
if (Dist(d, y) < k && H[d] <= H[y]) return -1;
d = x;
while (Dist(d, y) >= k)
{
if (le[0][d] == -1) break;
d = le[0][d];
}
if (Dist(d, y) < k && H[d] <= H[y]) return -1;
swap(x, y);
d = x;
while (Dist(d, y) >= k)
{
if (ri[0][d] == -1) break;
d = ri[0][d];
}
if (Dist(d, y) < k && H[d] <= H[y]) return 1;
d = x;
while (Dist(d, y) >= k)
{
if (le[0][d] == -1) break;
d = le[0][d];
}
if (Dist(d, y) < k && H[d] <= H[y]) return 1;
return 0;
}
signed main()
{
int n, k, q;
cin >> n >> k >> q;
vector<int> r(n);
for (int i = 0; i < n; i++) cin >> r[i];
init(k, r);
while (q--)
{
int x, y;
cin >> x >> y;
cout << compare_plants(x, y) << endl;
}
}