Submission #1289363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289363		mariaclara	Comparing Plants (IOI20_plants)	C++17	44 / 100	606 ms	18248 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];
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);
    }
}

int compare_plants(int x, int y) {
    if(ord[x] < ord[y]) return 1;
    return -1;
}

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