Submission #1289746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289746		mariaclara	Comparing Plants (IOI20_plants)	C++17	100 / 100	1028 ms	90412 KiB

plants

#include "plants.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
const int MAXN = 8e5+5;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int n, k, lz1[MAXN], lz2[MAXN];
pii seg1[MAXN], seg2[MAXN];
pii ml[20][MAXN], mr[20][MAXN];
vi v, ord;

void build(int node, int l, int r) {
    if(l == r) {
        seg1[node] = mk(v[l],l);
        seg2[node] = mk(1,l);
        return;
    }
    int mid = (l+r)/2;
    build(2*node, l, mid);
    build(2*node+1, mid+1, r);
    seg1[node] = min(seg1[2*node], seg1[2*node+1]);
    seg2[node] = min(seg2[2*node], seg2[2*node+1]);
}

void prop1(int node, int flag) {
    seg1[node].fr += lz1[node];
    if(flag) {
        lz1[2*node] += lz1[node];
        lz1[2*node+1] += lz1[node];
    }
    lz1[node] = 0;
}

void update1(int node, int l, int r, int p, int q, int val) {
    if(p < 0) update1(node, l, r, p+n, n-1, val), p = 0;

    prop1(node, l != r);

    if(r < p or q < l) return;
    if(p <= l and r <= q) {
        lz1[node] = val;
        prop1(node, l != r);
        return;
    }

    int mid = (l+r)/2;
    update1(2*node, l, mid, p, q, val);
    update1(2*node+1, mid+1, r, p, q, val);

    seg1[node] = min(seg1[2*node], seg1[2*node+1]);
}

void prop2(int node, int flag) {
    seg2[node].fr += lz2[node];
    if(flag) {
        lz2[2*node] += lz2[node];
        lz2[2*node+1] += lz2[node];
    }
    lz2[node] = 0;
}

void update2(int node, int l, int r, int p, int q, int val) {
    if(q >= n) update2(node, l, r, 0, q-n, val), q = n-1;

    prop2(node, l != r);

    if(r < p or q < l) return;
    if(p <= l and r <= q) {
        lz2[node] = val;
        prop2(node, l != r);
        return;
    }

    int mid = (l+r)/2;
    update2(2*node, l, mid, p, q, val);
    update2(2*node+1, mid+1, r, p, q, val);

    seg2[node] = min(seg2[2*node], seg2[2*node+1]);
}

void init(int K, vector<int> r) {
	n = sz(r);
    v = r;
    k = K;
    ord.resize(n);

    build(1,0,n-1);

    for(int t = 0; t < n; t++) {
        while(seg1[1].fr == 0) {
            update2(1, 0, n-1, seg1[1].sc+1, seg1[1].sc+k-1, 1);
            update2(1, 0, n-1, seg1[1].sc, seg1[1].sc, -1);
            update1(1, 0, n-1, seg1[1].sc, seg1[1].sc, 1e9);
        }
        int at = seg2[1].sc;
        ord[at] = t;
        update2(1, 0, n-1, at+1, at+k-1, -1);
        update2(1, 0, n-1, at, at, 1e9);
        update1(1, 0, n-1, at-k+1, at-1, -1);
    }

    set<pii> viz;

    for(int i = 1; i < k; i++) viz.insert({ord[i], i});

    for(int i = 0; i < n; i++) {
        auto ptr = viz.lower_bound({ord[i], i});
        if(ptr == viz.end()) mr[0][i] = {i, 0};
        else mr[0][i] = {(*ptr).sc, ((*ptr).sc-i+n)%n};
        viz.erase({ord[(i+1)%n], (i+1)%n});
        viz.insert({ord[(i+k)%n], (i+k)%n});
    }

    viz.clear();

    for(int i = n-1; i >= n-k+1; i--) viz.insert({ord[i], i});

    for(int i = 0; i < n; i++) {
        auto ptr = viz.lower_bound({ord[i], i});
        if(ptr == viz.end()) ml[0][i] = {i,0};
        else ml[0][i] = {(*ptr).sc, (i-(*ptr).sc+n)%n};
        viz.erase({ord[(i-k+1+n)%n], (i-k+1+n)%n});
        viz.insert({ord[i], i});
    }

    for(int b = 1; b < 20; b++){
        for(int i = 0; i < n; i++) {
            ml[b][i] = ml[b-1][ml[b-1][i].fr];
            ml[b][i].sc = min(n, ml[b][i].sc + ml[b-1][i].sc);
            mr[b][i] = mr[b-1][mr[b-1][i].fr];
            mr[b][i].sc = min(n, mr[b][i].sc + mr[b-1][i].sc);
        }
    }
}

int compare_plants(int x, int y) {
    int rsp = 1;
    if(ord[x] > ord[y]) rsp = -1, swap(x, y);

    for(int b = 19, X = x, atd = 0, dist = (y-x+n)%n; b >= 0; b--) {
        if(ord[mr[b][X].fr] <= ord[y]) atd += mr[b][X].sc, X = mr[b][X].fr;
        if(atd >= dist) return rsp;
    }

    for(int b = 19, X = x, atd = 0, dist = (x-y+n)%n; b >= 0; b--) {
        if(ord[ml[b][X].fr] <= ord[y]) atd += ml[b][X].sc, X = ml[b][X].fr;
        if(atd >= dist) return rsp;
    }

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 11 / 11
• Subtask 6: 15 / 15
• Subtask 7: 25 / 25