oj.uz

Submission #311579

# Submission time Handle Problem Language Result Execution time Memory
311579 2020-10-10T17:08:56 Z IgorI Comparing Plants (IOI20_plants) C++17
27 / 100
 4000 ms 91128 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)
{
    if (l < 0 || r > n)
    {
        if (l < 0) l += n;
        if (r > n) r -= n;
        pair<ll, int> a = Get2(l, n);
        pair<ll, int> b = Get2(0, r);
        if (a.first < INF) return a.second;
        if (b.first < INF) return b.second;
        return -1;
    }
    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];
    }
    #ifdef LOCAL
    for (int i = 0; i < n; i++)
    {
        cout << H[i] << " ";
    }
    cout << endl;
    #endif // LOCAL
    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;
    }
    ll d, dist;
    d = x;
    dist = y - x;
    for (int j = 0; j >= 0 && Dist(d, y) >= k; )
    {
        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] == INF);
    }

    d = x;
    dist = x - y + n;
    for (int j = 0; j >= 0 && Dist(d, y) >= k; )
    {
        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] == INF);
    }

    swap(x, y);
    d = x;
    dist = y - x + n;
    for (int j = 0; j >= 0 && Dist(d, y) >= k;)
    {
        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] == INF);
    }

    d = x;
    dist = x - y;
    for (int j = 0; j >= 0 && Dist(d, y) >= k;)
    {
        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] == INF);
    }

    return 0;
}

#ifdef LOCAL
signed 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 74 ms 3448 KB Output is correct
7 Correct 512 ms 12764 KB Output is correct
8 Correct 606 ms 90872 KB Output is correct
9 Correct 958 ms 90872 KB Output is correct
10 Correct 3967 ms 90916 KB Output is correct
11 Execution timed out 4075 ms 90872 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 5 ms 1152 KB Output is correct
7 Correct 88 ms 5880 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 5 ms 1152 KB Output is correct
10 Correct 94 ms 5880 KB Output is correct
11 Correct 85 ms 6008 KB Output is correct
12 Correct 84 ms 6008 KB Output is correct
13 Correct 88 ms 5880 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 768 KB Output is correct
6 Correct 5 ms 1152 KB Output is correct
7 Correct 88 ms 5880 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 5 ms 1152 KB Output is correct
10 Correct 94 ms 5880 KB Output is correct
11 Correct 85 ms 6008 KB Output is correct
12 Correct 84 ms 6008 KB Output is correct
13 Correct 88 ms 5880 KB Output is correct
14 Correct 159 ms 12872 KB Output is correct
15 Correct 1315 ms 91004 KB Output is correct
16 Correct 159 ms 12768 KB Output is correct
17 Correct 1324 ms 91000 KB Output is correct
18 Correct 824 ms 90940 KB Output is correct
19 Correct 811 ms 91128 KB Output is correct
20 Correct 1130 ms 90872 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 1040 ms 4316 KB Output isn't correct
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 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 640 KB Output is correct
5 Correct 3 ms 1024 KB Output is correct
6 Correct 1640 ms 90872 KB Output is correct
7 Correct 2366 ms 90836 KB Output is correct
8 Correct 1471 ms 90872 KB Output is correct
9 Correct 1343 ms 90872 KB Output is correct
10 Execution timed out 4086 ms 91000 KB Time limit exceeded
11 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 74 ms 3448 KB Output is correct
7 Correct 512 ms 12764 KB Output is correct
8 Correct 606 ms 90872 KB Output is correct
9 Correct 958 ms 90872 KB Output is correct
10 Correct 3967 ms 90916 KB Output is correct
11 Execution timed out 4075 ms 90872 KB Time limit exceeded
12 Halted 0 ms 0 KB -