oj.uz

Submission #311561

# Submission time Handle Problem Language Result Execution time Memory
311561 2020-10-10T16:19:27 Z IgorI Comparing Plants (IOI20_plants) C++17
27 / 100
 1201 ms 49300 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++)
    {
        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;
    }
    int d, dist;
    d = x;
    dist = y - x;
    for (int j = 0; j >= 0; )
    {
        if (ri[j][d] <= dist)
        {
            dist -= ri[j][d];
            d += ri[j][d];
            d = (d % n + n) % n;
        }
        else break;
    }
    assert(dist <= Dist(d, y));

    if (Dist(d, y) < k && H[d] <= H[y]) return -1;

    if (Dist(d, y) >= k)
    {
        assert(ri[0][d] > dist);
    }

    d = x;
    dist = x - y + n;
    for (int j = 0; j >= 0; )
    {
        if (le[j][d] <= dist)
        {
            dist -= le[j][d];
            d -= le[j][d];
            d = (d % n + n) % n;
        }
        else break;
    }
    assert(dist <= Dist(d, y));

    if (Dist(d, y) < k && H[d] <= H[y]) return -1;

    if (Dist(d, y) >= k)
    {
        assert(le[0][d] > dist);
    }

    swap(x, y);
    d = x;
    dist = x - y;
    for (int j = 0; j >= 0;)
    {
        if (ri[j][d] <= dist)
        {
            dist -= ri[j][d];
            d += ri[j][d];
            d = (d % n + n) % n;
        }
        else break;
    }
    assert(dist <= Dist(d, y));

    if (Dist(d, y) < k && H[d] <= H[y]) return 1;

    if (Dist(d, y) >= k)
    {
        assert(ri[0][d] > dist);
    }

    d = x;
    dist = y - x + n;
    for (int j = 0; j >= 0;)
    {
        if (le[j][d] <= dist)
        {
            dist -= le[j][d];
            d -= le[j][d];
            d = (d % n + n) % n;
        }
        else break;
    }
    assert(dist <= Dist(d, y));

    if (Dist(d, y) < k && H[d] <= H[y]) return 1;

    if (Dist(d, y) >= k)
    {
        assert(le[0][d] > dist);
    }

    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 9 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 6 ms 896 KB Output is correct
7 Correct 91 ms 4732 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 87 ms 4728 KB Output is correct
11 Correct 83 ms 4600 KB Output is correct
12 Correct 87 ms 4932 KB Output is correct
13 Correct 87 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 6 ms 896 KB Output is correct
7 Correct 91 ms 4732 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 87 ms 4728 KB Output is correct
11 Correct 83 ms 4600 KB Output is correct
12 Correct 87 ms 4932 KB Output is correct
13 Correct 87 ms 4728 KB Output is correct
14 Correct 151 ms 8384 KB Output is correct
15 Correct 1201 ms 49300 KB Output is correct
16 Correct 158 ms 8420 KB Output is correct
17 Correct 1196 ms 49272 KB Output is correct
18 Correct 771 ms 49272 KB Output is correct
19 Correct 763 ms 49272 KB Output is correct
20 Correct 1042 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 66 ms 6648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 9 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.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 9 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 9 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -