Submission #1148721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148721		onbert	Comparing Plants (IOI20_plants)	C++20	0 / 100	0 ms	396 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5, maxN = 8e5 + 5, 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], L[maxn], R[maxn];;

int dp[305][305];

void init(int K, std::vector<int> 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] = R[cur] = -1;
        pair<int,int> val = qry(cur-k+1, cur-1, 1);
        if (val.first >= 0) L[cur] = val.second;
        val = qry(cur+1, cur+k-1, 1);
        if (val.first >= 0) R[cur] = val.second;
        update(cur, cur, cur + INF, 1);
        // cout << cur << " " << L[cur] << " " << R[cur] << endl;
    }

    for (int i=0;i<n;i++) {
        for (int j=1;j<=k-1;j++) {
            int J = (i+j)%n;
            if (ord[i] > ord[J]) dp[i][J] = 1, dp[J][i] = -1;
            else dp[i][J] = -1, dp[J][i] = 1;
        }
    }
    // for (int i=0;i<n;i++) {
    //     for (int j=0;j<n;j++) cout << dp[i][j] << " "; cout << endl;
    // }
    for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++) for (int k=0;k<n;k++) {
            if (dp[j][i] == dp[i][k]) dp[j][k] = dp[j][i];
        }
    }
    // for (int i=0;i<n;i++) cout << qry(i, i, 1).second << " "; cout << endl;
}

int compare_plants(int x, int y) {
    return dp[x][y];
    int ans = 1;
	if (ord[x] < ord[y]) swap(x, y), ans = -1;
    int cur = x;
    bool dead = false;
    while ((y - cur + n)%n > k-1) {
        if (R[cur] == -1) {
            dead = true;
            break;
        }
        cur = R[cur];
    }
    if (!dead && ord[cur] >= ord[y]) return ans;
    // cout << x << " " << y << endl;
    cur = x, dead = false;
    // cout << cur << " " << y << endl;
    while ((cur - y + n)%n > k-1) {
        if (L[cur] == -1) {
            dead = true;
            break;
        }
        cur = L[cur];
    }
    // cout << x << " " << y << " " << cur << " " << dead << endl;
    if (!dead && ord[cur] >= ord[y]) return ans;
    return 0;
}

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