Submission #1065049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065049		Zicrus	Comparing Plants (IOI20_plants)	C++17	14 / 100	4046 ms	25936 KiB

plants

#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
• Subtask 2: 14 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25