oj.uz

Submission #311464

# Submission time Handle Problem Language Result Execution time Memory
311464 2020-10-10T09:49:11 Z IgorI Comparing Plants (IOI20_plants) C++17
44 / 100
 737 ms 13016 KB 
#include <bits/stdc++.h>

using namespace std;


const int N = 500000;
const int INF = 1e9;

int c;
int n;
int H[N];

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);
    }
}

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);
    }
    h1[i] = c--;
    CAdd(i - k + 1, i, -1);
    CAdd(i, i + 1, INF);
}

void init(int k, vector<int> r)
{
    n = r.size();
    vector<int> h1(n);
    c = n;

    Build(0, n, 0, r);

    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];
        //cout << H[i] << " ";
    }
    //cout << endl;
}

int compare_plants(int x, int y)
{
    if (H[x] > H[y]) return 1;
    return -1;
}

#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 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 81 ms 3576 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 80 ms 3520 KB Output is correct
11 Correct 77 ms 3320 KB Output is correct
12 Correct 79 ms 3648 KB Output is correct
13 Correct 79 ms 3520 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 81 ms 3576 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 80 ms 3520 KB Output is correct
11 Correct 77 ms 3320 KB Output is correct
12 Correct 79 ms 3648 KB Output is correct
13 Correct 79 ms 3520 KB Output is correct
14 Correct 120 ms 4316 KB Output is correct
15 Correct 737 ms 12152 KB Output is correct
16 Correct 120 ms 4192 KB Output is correct
17 Correct 718 ms 12024 KB Output is correct
18 Correct 505 ms 12024 KB Output is correct
19 Correct 504 ms 12092 KB Output is correct
20 Correct 645 ms 12024 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 74 ms 3256 KB Output is correct
4 Correct 411 ms 13016 KB Output is correct
5 Correct 457 ms 12280 KB Output is correct
6 Correct 624 ms 12152 KB Output is correct
7 Correct 704 ms 12024 KB Output is correct
8 Correct 715 ms 12024 KB Output is correct
9 Correct 416 ms 12024 KB Output is correct
10 Correct 418 ms 12024 KB Output is correct
11 Correct 360 ms 11928 KB Output is correct
12 Correct 413 ms 12024 KB Output is correct
13 Correct 496 ms 12152 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -