oj.uz

Submission #405387

# Submission time Handle Problem Language Result Execution time Memory
405387 2021-05-16T10:24:35 Z tiberiu Comparing Plants (IOI20_plants) C++14
44 / 100
 615 ms 21084 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;
    }
//    cerr << l << ' ' << r << ' ' << nl << ' ' << nr << endl;

    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) {

//    cerr << x << endl;
    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);
//    for (int i = 0; i < N; i++)
//        cout << query(i, i).first << ' ';
//    cout << endl;
//    cerr << x << endl;
}

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]);
    }
//    cerr << "Gen complete!" << endl;
}

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

    gen(k, r);

	return;
}

int compare_plants(int x, int y) {
	return (hGen[x] < hGen[y] ? -1 : 1);
}

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 Incorrect 1 ms 332 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 332 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 4 ms 428 KB Output is correct
7 Correct 96 ms 5316 KB Output is correct
8 Correct 3 ms 316 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 68 ms 5320 KB Output is correct
11 Correct 68 ms 5188 KB Output is correct
12 Correct 78 ms 5400 KB Output is correct
13 Correct 74 ms 5212 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 4 ms 428 KB Output is correct
7 Correct 96 ms 5316 KB Output is correct
8 Correct 3 ms 316 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 68 ms 5320 KB Output is correct
11 Correct 68 ms 5188 KB Output is correct
12 Correct 78 ms 5400 KB Output is correct
13 Correct 74 ms 5212 KB Output is correct
14 Correct 106 ms 6412 KB Output is correct
15 Correct 595 ms 15684 KB Output is correct
16 Correct 112 ms 6408 KB Output is correct
17 Correct 582 ms 15560 KB Output is correct
18 Correct 469 ms 15172 KB Output is correct
19 Correct 410 ms 15908 KB Output is correct
20 Correct 535 ms 15732 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 61 ms 4960 KB Output is correct
4 Correct 356 ms 15560 KB Output is correct
5 Correct 415 ms 15048 KB Output is correct
6 Correct 527 ms 15176 KB Output is correct
7 Correct 615 ms 15560 KB Output is correct
8 Correct 608 ms 15640 KB Output is correct
9 Correct 379 ms 15124 KB Output is correct
10 Correct 400 ms 15420 KB Output is correct
11 Correct 318 ms 21084 KB Output is correct
12 Correct 335 ms 15008 KB Output is correct
13 Correct 467 ms 15064 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 300 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 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 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 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -