oj.uz

Submission #1065058

# Submission time Handle Problem Language Result Execution time Memory
1065058 2024-08-18T21:53:21 Z Zicrus Comparing Plants (IOI20_plants) C++17
0 / 100
 1 ms 604 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;
    laz[i] = 0;
    i /= 2;
    while (i > 0) {
        seg[i] = min(seg[2*i]-laz[2*i], seg[2*i+1]-laz[2*i+1]) - laz[i];
        laz[i] = 0;
        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 348 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
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 Runtime error 1 ms 604 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

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 Runtime error 1 ms 604 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 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 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 Runtime error 0 ms 348 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -