oj.uz

Submission #1065054

# Submission time Handle Problem Language Result Execution time Memory
1065054 2024-08-18T21:50:47 Z Zicrus Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 22096 KB 
#include <bits/stdc++.h>
#include "plants.h"
using namespace std;

typedef long long ll;

ll n, pow2, val;
vector<ll> seg, laz, a;

ll segFind(ll low, ll high, ll nl = 0, ll nh = pow2-1, ll i = 1) {
    if (i >= pow2) return (seg[i] - laz[i] == 0) ? i-pow2 : -1;
    laz[2*i] += laz[i];
    laz[2*i+1] += laz[i];
    seg[i] -= laz[i];
    laz[i] = 0;
    if (low <= nl && high >= nh) {
        ll v = segFind(low, high, nl, (nl+nh)/2, 2*i);
        if (v != -1) return v;
        return segFind(low, high, (nl+nh)/2+1, nh, 2*i+1);
    }
    if (low <= (nl+nh)/2) {
        ll v = segFind(low, high, nl, (nl+nh)/2, 2*i);
        if (v != -1) return v;
    }
    if (high > (nl+nh)/2) {
        return segFind(low, high, (nl+nh)/2+1, nh, 2*i+1);
    }
    return -1;
}

void segDec(ll low, ll high, ll nl = 0, ll nh = pow2-1, ll i = 1) {
    if (low <= nl && high >= nh) {
        laz[i]++;
        return;
    }
    laz[2*i] += laz[i];
    laz[2*i+1] += laz[i];
    seg[i] -= laz[i];
    laz[i] = 0;
    if (low <= (nl+nh)/2) segDec(low, high, nl, (nl+nh)/2, 2*i);
    if (high > (nl+nh)/2) segDec(low, high, (nl+nh+1)/2, nh, 2*i+1);
    seg[i] = min(seg[2*i]-laz[2*i], seg[2*i+1]-laz[2*i+1]);
}

void segSet(ll i, ll v) {
    i += pow2;
    seg[i] = v;
    i /= 2;
    while (i > 0) {
        seg[i] = min(seg[2*i], seg[2*i+1]);
        i /= 2;
    }
}

void init(int k, vector<int> r) {
    n = val = r.size();
    a = vector<ll>(n);
    pow2 = 1ll << (ll)ceil(log2(2*n));
    seg = vector<ll>(2*pow2);
    laz = vector<ll>(2*pow2);
    for (int i = 0; i < n; i++) {
        seg[pow2+i] = r[i];
        seg[pow2+n+i] = r[i];
    }
    for (int i = pow2-1; i > 0; i--) {
        seg[i] = min(seg[2*i], seg[2*i+1]);
    }

    while (val > 0) {
        ll id = segFind(n, 2*n-1);
        id = segFind(id-k+1, id);
        id %= n;
        a[id] = val--;
        segSet(id, 1ll << 62ll);
        segSet(id+n, 1ll << 62ll);
        if (id > 0) segDec(max(0ll, id-k+1), id-1);
        if (id+2*n-k+1 <= 2*n-1) segDec(id+2*n-k+1, 2*n-1);
        segDec(id+n-k+1, id+n-1);
    }
    return;
}

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

#ifdef TEST
#include "grader.cpp"
#endif

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Runtime error 0 ms 348 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 9 ms 348 KB Output is correct
7 Correct 209 ms 3632 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 8 ms 348 KB Output is correct
10 Correct 210 ms 3632 KB Output is correct
11 Correct 177 ms 3664 KB Output is correct
12 Correct 170 ms 3928 KB Output is correct
13 Correct 239 ms 3652 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 9 ms 348 KB Output is correct
7 Correct 209 ms 3632 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 8 ms 348 KB Output is correct
10 Correct 210 ms 3632 KB Output is correct
11 Correct 177 ms 3664 KB Output is correct
12 Correct 170 ms 3928 KB Output is correct
13 Correct 239 ms 3652 KB Output is correct
14 Correct 1922 ms 5412 KB Output is correct
15 Execution timed out 4038 ms 22096 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1 ms 348 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 0 ms 348 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Runtime error 0 ms 348 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -