Submission #1148737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148737		onbert	Comparing Plants (IOI20_plants)	C++20	100 / 100	1100 ms	94352 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5, maxN = 8e5 + 5, lg = 18, INF = 1e6;
int n, k;
int a[maxn];

pair<int,int> seg[maxN][2];
int lazy[maxN][2];
void build(int id, int l, int r, int j) {
    lazy[id][j] = 0;
    if (l == r) {
        if (j == 0) seg[id][j] = {a[l], l};
        else seg[id][j] = {-INF, l};
        return;
    }
    int mid = (l+r)/2;
    build(id*2, l, mid, j); build(id*2+1, mid+1, r, j);
    seg[id][j] = max(seg[id*2][j], seg[id*2+1][j]);
}
void push(int id, int j) {
    seg[id][j].first += lazy[id][j];
    if (id*2 < maxN) lazy[id*2][j] += lazy[id][j];
    if (id*2+1 < maxN) lazy[id*2+1][j] += lazy[id][j];
    lazy[id][j] = 0;
}
void upd(int id, int l, int r, int findl, int findr, int val, int j) {
    push(id, j);
    if (r < findl || findr < l) return;
    if (findl <= l && r <= findr) {
        lazy[id][j] += val;
        push(id, j);
        return;
    }
    int mid = (l+r)/2;
    upd(id*2, l, mid, findl, findr, val, j); upd(id*2+1, mid+1, r, findl, findr, val, j);
    seg[id][j] = max(seg[id*2][j], seg[id*2+1][j]);
}
pair<int,int> mx(int id, int l, int r, int findl, int findr, int j) {
    push(id, j);
    if (r < findl || findr<l) return {-INF, -1};
    if (findl <= l && r <= findr) return seg[id][j];
    int mid = (l+r)/2;
    return max(mx(id*2, l, mid, findl, findr, j), mx(id*2+1, mid+1, r, findl, findr, j));
}
pair<int,int> qry(int l, int r, int j) {
    l = (l + n) % n, r = (r + n) % n;
    if (l <= r) return mx(1, 0, n-1, l, r, j);
    return max(mx(1, 0, n-1, l, n-1, j), mx(1, 0, n-1, 0, r, j));
}
void update(int l, int r, int val, int j) {
    l = (l + n) % n, r = (r + n) % n;
    if (l <= r) upd(1, 0, n-1, l, r, val, j);
    else {
        upd(1, 0, n-1, l, n-1, val, j);
        upd(1, 0, n-1, 0, r, val, j);
    }
}


int ord[maxn], pos[maxn];
int L[maxn][lg], R[maxn][lg];

void init(int32_t K, std::vector<int32_t> r) {
	n = r.size(), k = K;
    for (int i=0;i<n;i++) a[i] = r[i];
    build(1, 0, n-1, 0); build(1, 0, n-1, 1);
    for (int i=0;i<n;i++) {
        pair<int,int> add = qry(0, n-1, 0);
        while (add.first == k-1) {
            int u = add.second;
            // cout << i << " " << add.first << " " << add.second << endl;
            update(u, u, -INF, 0);
            update(u, u, INF, 1);
            update(u+1, u+k-1, -1, 1);
            add = qry(0, n-1, 0);
        }
        int nw = qry(0, n-1, 1).second;
        ord[nw] = i;
        pos[i] = nw;
        // cout << nw << endl;
        update(nw, nw, -INF, 1);
        update(nw+1, nw+k-1, 1, 1);
        update(nw-k+1, nw-1, 1, 0);
    }
    // for (int i=0;i<n;i++) cout << ord[i] << " "; cout << endl;
    build(1, 0, n-1, 1);
    for (int i=0;i<n;i++) {
        int cur = pos[i];
        L[cur][0] = R[cur][0] = INF;
        pair<int,int> val = qry(cur-k+1, cur-1, 1);
        if (val.first >= 0) L[cur][0] = (cur - val.second + n) % n;
        val = qry(cur+1, cur+k-1, 1);
        if (val.first >= 0) R[cur][0] = (val.second - cur + n) % n;
        update(cur, cur, i + INF, 1);
        // cout << cur << " " << L[cur] << " " << R[cur] << endl;
    }
    // for (int i=0;i<n;i++) cout << L[i][0] << " " ; cout << endl;

    for (int i=1;i<lg;i++) {
        for (int j=0;j<n;j++) {
            L[j][i] = L[j][i-1] + L[((j - L[j][i-1]) % n + n) % n][i-1];
            R[j][i] = R[j][i-1] + R[(j + R[j][i-1]) % n][i-1];
        }
        // if (i <= 2) {
        //     for (int j=0;j<n;j++) cout << L[j][i] << " "; cout << endl;
        // }
    }
    // cout << "test\n";
    // for (int i=0;i<n;i++) cout << qry(i, i, 1).second << " "; cout << endl;
}

int32_t compare_plants(int32_t x, int32_t y) {
    int ans = 1;
	if (ord[x] < ord[y]) swap(x, y), ans = -1;
    if ((y - x + n) % n <= k-1 || (x - y + n) % n <= k-1) return ans;
    
    int target = ((y - k) - x + n + n) % n, u = x, cur = 0;
    for (int i=lg-1;i>=0;i--) {
        if (cur + R[u][i] <= target) cur += R[u][i], u = (u + R[u][i]) % n;
    }
    if (R[u][0] != INF) {
        u = (u + R[u][0]) % n;
        if ((y - u + n) % n <= k-1 && ord[u] > ord[y]) return ans;
    }
    
    target = (x - (y + k) + n + n) % n, u = x, cur = 0;
    for (int i=lg-1;i>=0;i--) {
        if (cur + L[u][i] <= target) cur += L[u][i], u = (u - L[u][i] + n) % n;
    }
    if (L[u][0] != INF) {
        u = (u - L[u][0] + n) % n;
        if ((u - y + n) % n <= k-1 && ord[u] > ord[y]) return ans;
    }

    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