oj.uz

Submission #311615

# Submission time Handle Problem Language Result Execution time Memory
311615 2020-10-10T19:02:19 Z IgorI Comparing Plants (IOI20_plants) C++17
25 / 100
 4000 ms 91896 KB 
#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)
    {
        pair<ll, int> a = Get2(l, n);
        pair<ll, int> b = Get2(0, r);
        if (min(a, b).first < INF)
            return min(a, b).second;
    }
    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;
}

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 66 ms 3448 KB Output is correct
7 Correct 199 ms 12764 KB Output is correct
8 Correct 632 ms 91036 KB Output is correct
9 Correct 691 ms 91000 KB Output is correct
10 Correct 1222 ms 91004 KB Output is correct
11 Execution timed out 4094 ms 90876 KB Time limit exceeded
12 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 768 KB Output is correct
6 Correct 21 ms 1152 KB Output is correct
7 Correct 502 ms 5880 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 21 ms 1144 KB Output is correct
10 Correct 480 ms 5880 KB Output is correct
11 Correct 282 ms 5880 KB Output is correct
12 Correct 278 ms 6008 KB Output is correct
13 Correct 605 ms 6136 KB Output is correct

Subtask #3
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 768 KB Output is correct
6 Correct 21 ms 1152 KB Output is correct
7 Correct 502 ms 5880 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 21 ms 1144 KB Output is correct
10 Correct 480 ms 5880 KB Output is correct
11 Correct 282 ms 5880 KB Output is correct
12 Correct 278 ms 6008 KB Output is correct
13 Correct 605 ms 6136 KB Output is correct
14 Execution timed out 4061 ms 6384 KB Time limit exceeded
15 Halted 0 ms 0 KB -

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 Correct 240 ms 4344 KB Output is correct
4 Execution timed out 4089 ms 91896 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.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 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 3 ms 768 KB Output is correct
7 Correct 20 ms 1408 KB Output is correct
8 Correct 18 ms 1408 KB Output is correct
9 Correct 24 ms 1408 KB Output is correct
10 Correct 17 ms 1408 KB Output is correct
11 Correct 23 ms 1408 KB Output is correct
12 Correct 20 ms 1408 KB Output is correct
13 Correct 18 ms 1408 KB Output is correct

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 640 KB Output is correct
5 Correct 6 ms 1152 KB Output is correct
6 Correct 1588 ms 90872 KB Output is correct
7 Execution timed out 4067 ms 30596 KB Time limit exceeded
8 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 66 ms 3448 KB Output is correct
7 Correct 199 ms 12764 KB Output is correct
8 Correct 632 ms 91036 KB Output is correct
9 Correct 691 ms 91000 KB Output is correct
10 Correct 1222 ms 91004 KB Output is correct
11 Execution timed out 4094 ms 90876 KB Time limit exceeded
12 Halted 0 ms 0 KB -