oj.uz

Submission #1065049

# Submission time Handle Problem Language Result Execution time Memory
1065049 2024-08-18T21:42:21 Z Zicrus Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 25936 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);
}

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 0 ms 344 KB Output is correct
2 Correct 1 ms 344 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 11 ms 612 KB Output is correct
7 Correct 209 ms 5520 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 8 ms 612 KB Output is correct
10 Correct 225 ms 5724 KB Output is correct
11 Correct 175 ms 5596 KB Output is correct
12 Correct 218 ms 5784 KB Output is correct
13 Correct 266 ms 5716 KB Output is correct

Subtask #3
0 / 13.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 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 11 ms 612 KB Output is correct
7 Correct 209 ms 5520 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 8 ms 612 KB Output is correct
10 Correct 225 ms 5724 KB Output is correct
11 Correct 175 ms 5596 KB Output is correct
12 Correct 218 ms 5784 KB Output is correct
13 Correct 266 ms 5716 KB Output is correct
14 Correct 1851 ms 7632 KB Output is correct
15 Execution timed out 4046 ms 25936 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 0 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 1 ms 344 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 0 ms 344 KB Output is correct
2 Correct 1 ms 344 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 -