oj.uz

Submission #311510

# Submission time Handle Problem Language Result Execution time Memory
311510 2020-10-10T14:36:42 Z IgorI Comparing Plants (IOI20_plants) C++17
27 / 100
 1176 ms 49400 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)
{
    if (Dist(x, y) < k)
    {
        if (H[x] <= H[y]) return -1;
        return 1;
    }
    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

# Verdict Execution time Memory 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
14.0 / 14.0

# Verdict Execution time Memory 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 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 5 ms 896 KB Output is correct
7 Correct 87 ms 4728 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 86 ms 4808 KB Output is correct
11 Correct 83 ms 4600 KB Output is correct
12 Correct 82 ms 4860 KB Output is correct
13 Correct 86 ms 4728 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory 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 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 5 ms 896 KB Output is correct
7 Correct 87 ms 4728 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 86 ms 4808 KB Output is correct
11 Correct 83 ms 4600 KB Output is correct
12 Correct 82 ms 4860 KB Output is correct
13 Correct 86 ms 4728 KB Output is correct
14 Correct 149 ms 8412 KB Output is correct
15 Correct 1176 ms 49208 KB Output is correct
16 Correct 147 ms 8412 KB Output is correct
17 Correct 1175 ms 49272 KB Output is correct
18 Correct 747 ms 49400 KB Output is correct
19 Correct 769 ms 49400 KB Output is correct
20 Correct 1039 ms 49272 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Runtime error 55 ms 3452 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Runtime error 1 ms 672 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory 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 -