oj.uz

Submission #311555

# Submission time Handle Problem Language Result Execution time Memory
311555 2020-10-10T16:09:12 Z IgorI Comparing Plants (IOI20_plants) C++17
27 / 100
 1327 ms 49248 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 = 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;

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

    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;

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

    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;

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

    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;

    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 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 105 ms 3472 KB Output is correct
7 Incorrect 187 ms 8320 KB Output isn't correct
8 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 93 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 89 ms 4728 KB Output is correct
11 Correct 87 ms 4592 KB Output is correct
12 Correct 85 ms 4856 KB Output is correct
13 Correct 88 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 93 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 89 ms 4728 KB Output is correct
11 Correct 87 ms 4592 KB Output is correct
12 Correct 85 ms 4856 KB Output is correct
13 Correct 88 ms 4728 KB Output is correct
14 Correct 174 ms 8392 KB Output is correct
15 Correct 1288 ms 49204 KB Output is correct
16 Correct 165 ms 8384 KB Output is correct
17 Correct 1327 ms 49212 KB Output is correct
18 Correct 800 ms 49248 KB Output is correct
19 Correct 834 ms 49200 KB Output is correct
20 Correct 1098 ms 49208 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 Incorrect 141 ms 4020 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 Incorrect 1 ms 640 KB Output isn't correct
6 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 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 672 KB Output is correct
5 Incorrect 3 ms 896 KB Output isn't correct
6 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 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 105 ms 3472 KB Output is correct
7 Incorrect 187 ms 8320 KB Output isn't correct
8 Halted 0 ms 0 KB -