oj.uz

답안 #311509

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
311509 2020-10-10T14:24:42 Z IgorI 식물 비교 (IOI20_plants) C++17
0 / 100
 1 ms 640 KB 
#include <bits/stdc++.h>

using namespace std;


const int N = 500000;
const int INF = 1e9;

int c;
int n;
int H[N];
int k;

pair<int, int> tree[4 * N];
int push[4 * N];

pair<int, int> Merge(pair<int, int> a, pair<int, 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<int, 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, int 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<int, int> a = Get(l, n);
        pair<int, int> b = Get(0, r);
        if (a.first == 0) return a.second;
        if (b.first == 0) return b.second;
        return -1;
    }
    pair<int, int> a = Get(l, r);
    if (a.first == 0) return a.second;
    return -1;
}

void CAdd(int l, int r, int x)
{
    if (l < 0)
    {
        l += n;
        Add(l, n, x);
        Add(0, r, x);
    }
    else
    {
        Add(l, r, x);
    }
}

pair<int, 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<int, 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)
{
    if (l < 0 || r > n)
    {
        if (l < 0) l += n;
        if (r > n) r -= n;
        pair<int, int> a = Get2(l, n);
        pair<int, int> b = Get2(0, r);
        if (a.first < INF) return a.second;
        if (b.first < INF) return b.second;
        return -1;
    }
    pair<int, 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;

int 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++)
    {
        le[0][i] = up_left[i];
        ri[0][i] = up_right[i];
    }
    for (int j = 1; j < LG; j++)
    {
        for (int i = 0; i < n; i++)
        {
            int t = le[j - 1][i];
            if (t == -1) le[j][i] = -1;
            else t = le[j - 1][t], le[j][i] = t;
            t = ri[j - 1][i];
            if (t == -1) ri[j][i] = -1;
            else t = ri[j - 1][t], ri[j][i] = t;
        }
    }
    for (int j = 0; j < LG; j++)
    {
        for (int i = 0; i < n; i++)
        {
            if (ri[j][i] != -1)
            {
                ri[j][i] = ri[j][i] - i;
                if (ri[j][i] < 0) ri[j][i] += n;
            }
            else ri[j][i] = INF;
            if (le[j][i] != -1)
            {
                le[j][i] = i - le[j][i];
                if (le[j][i] < 0) le[j][i] += n;
            }
            else le[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)
{
    int d, dist;
    d = x;
    dist = y - x;
    for (int j = LG - 1; j >= 0; j--)
    {
        if (ri[j][d] <= dist)
        {
            dist -= ri[j][d];
            d += ri[j][d];
            if (d >= n) d -= n;
        }
    }
    if (Dist(d, y) < k && H[d] <= H[y]) return -1;
    d = x;
    dist = x - y + n;
    for (int j = LG - 1; j >= 0; j--)
    {
        if (le[j][d] <= dist)
        {
            dist -= le[j][d];
            d -= le[j][d];
            if (d < 0) d += n;
        }
    }
    if (Dist(d, y) < k && H[d] <= H[y]) return -1;

    swap(x, y);
    d = x;
    dist = x - y;
    for (int j = LG - 1; j >= 0; j--)
    {
        if (ri[j][d] <= dist)
        {
            dist -= ri[j][d];
            d += ri[j][d];
            if (d >= n) d -= n;
        }
    }
    if (Dist(d, y) < k && H[d] <= H[y]) return 1;
    d = x;
    dist = y - x + n;
    for (int j = LG - 1; j >= 0; j--)
    {
        if (le[j][d] <= dist)
        {
            dist -= le[j][d];
            d -= le[j][d];
            if (d < 0) d += n;
        }
    }
    if (Dist(d, y) < k && H[d] <= H[y]) return 1;
    exit(200);
    return 0;
}

#ifdef LOCAL
int 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;
    }
}
#endif

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Runtime error 1 ms 640 KB Execution failed because the return code was nonzero
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Runtime error 1 ms 640 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Runtime error 1 ms 640 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 640 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Runtime error 1 ms 640 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Runtime error 1 ms 640 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Runtime error 1 ms 640 KB Execution failed because the return code was nonzero
5 Halted 0 ms 0 KB -