oj.uz

Submission #405404

# Submission time Handle Problem Language Result Execution time Memory
405404 2021-05-16T10:55:03 Z tiberiu Comparing Plants (IOI20_plants) C++14
25 / 100
 4000 ms 19764 KB 
#include "plants.h"
#include <iostream>

using namespace std;

const int MAX_N = 2e5;

int N, K;

int v[MAX_N], hGen[MAX_N];
int aint_mn[4 * MAX_N];
int aint_pos[4 * MAX_N];
int aint_lazy[4 * MAX_N];

int cval;

void propag(int n, int nl, int nr) {
    aint_mn[n * 2 + 1] += aint_lazy[n];
    aint_lazy[n * 2 + 1] += aint_lazy[n];
    aint_mn[n * 2 + 2] += aint_lazy[n];
    aint_lazy[n * 2 + 2] += aint_lazy[n];
    aint_lazy[n] = 0;
}

void init_aint(int n = 0, int nl = 0, int nr = 0) {
    if (n == 0) nr = N - 1;

    aint_pos[n] = nl;

    if (nl < nr) {
        int mid = (nl + nr) / 2;
        init_aint(n * 2 + 1, nl, mid);
        init_aint(n * 2 + 2, mid + 1, nr);
    }
}

pair<int, int> query(int l, int r, int n = 0, int nl = 0, int nr = 0) {
    if (n == 0) nr = N - 1;

    if (l == nl && r == nr) {
        return {aint_mn[n], aint_pos[n]};
    }

    propag(n, nl, nr);

    pair<int, int> q1, q2;
    int mid = (nl + nr) / 2;

    if (r <= mid)
        return query(l, r, n * 2 + 1, nl, mid);
    else if (l > mid)
        return query(l, r, n * 2 + 2, mid + 1, nr);
    else {
        q1 = query(l, mid, n * 2 + 1, nl, mid);
        q2 = query(mid + 1, r, n * 2 + 2, mid + 1, nr);
        return min(q1, q2);
    }
}

void update(int l, int r, int val, int n = 0, int nl = 0, int nr = 0) {
    if (n == 0) nr = N - 1;

    if (l == nl && r == nr) {
        aint_mn[n] += val;
        aint_lazy[n] += val;
        return;
    }

    propag(n, nl, nr);

    int mid = (nl + nr) / 2;

    if (l <= mid)
        update(l, min(mid, r), val, n * 2 + 1, nl, mid);
    if (r > mid)
        update(max(mid + 1, l), r, val, n * 2 + 2, mid + 1, nr);

    if (aint_mn[n * 2 + 1] < aint_mn[n * 2 + 2]) {
        aint_mn[n] = aint_mn[n * 2 + 1];
        aint_pos[n] = aint_pos[n * 2 + 1];
    } else {
        aint_mn[n] = aint_mn[n * 2 + 2];
        aint_pos[n] = aint_pos[n * 2 + 2];
    }
}

void solve(int x) {
    if (x >= K - 1) {
        pair<int, int> q = query(x - K + 1, x - 1);
        if (q.first == 0) {
            solve(q.second);
            solve(x);
            return;
        }
    } else {
        pair<int, int> q = query(N + x - K + 1, N - 1);

        if (q.first != 0 && x > 0)
            q = query(0, x - 1);
        if (q.first == 0) {
            solve(q.second);
            solve(x);
            return;
        }
    }

    hGen[x] = cval;
    cval--;

    if (x >= K - 1) {
        update(x - K + 1, x - 1, -1);
    } else {
        if (x > 0)
            update(0, x - 1, -1);
        update(N + x - K + 1, N - 1, -1);
    }
    update(x, x, +1000000);
}

void gen(int k, vector<int> r) {
    init_aint();

    for (int i = 0; i < N; i++) {
        update(i, i, r[i]);
    }

    cval = N;

    while (aint_mn[0] == 0) {
        solve(aint_pos[0]);
    }
}

int leftV[MAX_N];
int rightV[MAX_N];

#include <set>

void calc_lr() {
    multiset<pair<int, int>> w;
    for (int i = N - K + 1; i < N; i++) {
        w.insert({hGen[i], i});
    }

    for (int i = 0; i < N; i++) {
        multiset<pair<int, int>>::iterator it = w.lower_bound({hGen[i], i});
        if (it != w.begin()) {
            it--;
            leftV[i] = it->second;
        } else
            leftV[i] = -1;
        int rmv = (N + i - K + 1) % N;
        w.erase({hGen[rmv], rmv});
        w.insert({hGen[i], i});
    }

    w.clear();
    for (int i = 0; i < K - 1; i++) {
        w.insert({hGen[i], i});
    }

    for (int i = N - 1; i >= 0; i--) {
        multiset<pair<int, int>>::iterator it = w.lower_bound({hGen[i], i});
        if (it != w.begin()) {
            it--;
            rightV[i] = it->second;
        } else
            rightV[i] = -1;
        int rmv = (N + i + K - 1) % N;
        w.erase({hGen[rmv], rmv});
        w.insert({hGen[i], i});
    }

}

void init(int k, std::vector<int> r) {
    K = k;
    N = r.size();

    gen(k, r);

    calc_lr();

	return;
}

int compare_plants(int x0, int y0) {
    int x = x0, y = y0;

    while ((y - x + N) % N >= K && rightV[x] != -1)
        x = rightV[x];
    if ((y - x + N) % N < K && hGen[x] > hGen[y])
        return 1;
    x = x0;

    while ((y - x + N) % N >= K && leftV[y] != -1)
        y = leftV[y];
    if ((y - x + N) % N < K && hGen[y] > hGen[x])
        return -1;
    y = y0;

    while ((x - y + N) % N >= K && leftV[x] != -1)
        x = leftV[x];
    if ((x - y + N) % N < K && hGen[x] > hGen[y])
        return 1;
    x = x0;

    while ((x - y + N) % N >= K && rightV[y] != -1)
        y = rightV[y];
    if ((x - y + N) % N < K && hGen[y] > hGen[x])
        return -1;
    y = y0;

	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 64 ms 4044 KB Output is correct
7 Correct 244 ms 6496 KB Output is correct
8 Correct 350 ms 15640 KB Output is correct
9 Correct 486 ms 15656 KB Output is correct
10 Correct 1630 ms 15820 KB Output is correct
11 Execution timed out 4070 ms 16712 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 308 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 5 ms 460 KB Output is correct
7 Correct 82 ms 4232 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Correct 76 ms 4224 KB Output is correct
11 Correct 288 ms 4120 KB Output is correct
12 Correct 300 ms 4332 KB Output is correct
13 Correct 77 ms 4328 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 5 ms 460 KB Output is correct
7 Correct 82 ms 4232 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Correct 76 ms 4224 KB Output is correct
11 Correct 288 ms 4120 KB Output is correct
12 Correct 300 ms 4332 KB Output is correct
13 Correct 77 ms 4328 KB Output is correct
14 Correct 133 ms 5408 KB Output is correct
15 Correct 1116 ms 19160 KB Output is correct
16 Correct 133 ms 5408 KB Output is correct
17 Correct 1135 ms 19128 KB Output is correct
18 Execution timed out 4066 ms 18060 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 345 ms 3804 KB Output is correct
4 Execution timed out 4019 ms 14012 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 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 20 ms 1288 KB Output is correct
8 Correct 16 ms 1252 KB Output is correct
9 Correct 30 ms 1200 KB Output is correct
10 Correct 16 ms 1288 KB Output is correct
11 Correct 20 ms 1212 KB Output is correct
12 Correct 21 ms 1232 KB Output is correct
13 Correct 15 ms 1304 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 745 ms 14896 KB Output is correct
7 Correct 1269 ms 15220 KB Output is correct
8 Correct 830 ms 15796 KB Output is correct
9 Correct 990 ms 19764 KB Output is correct
10 Correct 3861 ms 15008 KB Output is correct
11 Execution timed out 4037 ms 19216 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 64 ms 4044 KB Output is correct
7 Correct 244 ms 6496 KB Output is correct
8 Correct 350 ms 15640 KB Output is correct
9 Correct 486 ms 15656 KB Output is correct
10 Correct 1630 ms 15820 KB Output is correct
11 Execution timed out 4070 ms 16712 KB Time limit exceeded
12 Halted 0 ms 0 KB -