Submission #1229350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229350		Hamed_Ghaffari	Comparing Plants (IOI20_plants)	C++20	49 / 100	363 ms	25860 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

#define X first
#define Y second
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)

const int MXN = 2e5+5;

namespace K2 {
    int n;
    vector<int> ps;
    inline int P(int i) { return i>=0 ? ps[i] : 0; }

    void init(int k, vector<int> r) {
        n = r.size();
        ps.push_back(r[0]);
        for(int i=1; i<n; i++)
            ps.push_back(ps.back()+r[i]);
    }

    int compare_plants(int x, int y) {
        if(P(y-1)-P(x-1)==0) return 1;
        if(P(y-1)-P(x-1)==y-x) return -1;
        if(P(n-1)-P(y-1)+P(x-1)==0) return -1;
        if(P(n-1)-P(y-1)+P(x-1)==n-(y-x)) return 1;
        return 0;
    }
}

int n, k, lz[MXN<<2];
pii seg[MXN<<2];

void build(int l=0, int r=n, int id=1) {
    seg[id] = {0, l};
    if(r-l == 1) return;
    build(l, mid, lc);
    build(mid, r, rc);
}
inline void apply(int x, int id) {
    seg[id].X += x;
    lz[id] += x;
}
inline void push(int id) {
    if(lz[id]) {
        apply(lz[id], lc);
        apply(lz[id], rc);
        lz[id] = 0;
    }
}
void upd(int s, int e, int x, int l=0, int r=n, int id=1) {
    if(s>=r || l>=e) return;
    if(s<=l && r<=e) {
        apply(x, id);
        return;
    }
    push(id);
    upd(s, e, x, l, mid, lc);
    upd(s, e, x, mid, r, rc);
    seg[id] = min(seg[lc], seg[rc]);
}
pii get(int s, int e, int l=0, int r=n, int id=1) {
    if(s>=r || l>=e) return pii(n, n);
    if(s<=l && r<=e) return seg[id];
    push(id);
    return min(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
}

int pos[MXN], timer;

vector<int> g[MXN];

inline void add(int u, int v) {
    g[u].push_back(v);
}

void rec(int i) {
    while(1) {
        pii d = i-k+1>=0 ? get(i-k+1, i) : min(get(0, i), get(n+(i-k+1), n));
        if(d.X) break;
        rec(d.Y);
    }
    pos[i] = ++timer;
    if(i-k+1>=0) upd(i-k+1, i, -1);
    else upd(0, i, -1), upd(n+(i-k+1), n, -1);
    upd(i, i+1, n);

    if(n<=300) {
        for(int j=i+1, t=0; t<k-1; (++j)%=n, t++)
            if(!pos[j])
                add(i, j);
        for(int j=(i+n-1)%n, t=0; t<k-1; (j+=n-1)%=n, t++)
            if(!pos[j])
                add(i, j);
    }
}

vector<bool> vis[MXN];

void dfs(int r, int v) {
    vis[r][v] = 1;
    for(int u : g[v])
        if(!vis[r][u])
            dfs(r, u);
}

void init(int k, vector<int> r) {
    ::k = k;
    if(k==2) return K2::init(k, r);
    n = r.size();
    build();
    for(int i=0; i<n; i++) upd(i, i+1, r[i]);
    while(seg[1].X==0)
        rec(seg[1].Y);
}

int compare_plants(int x, int y) {
    if(k==2) return K2::compare_plants(x, y);
    if(n<=300) {
        if(vis[x].empty()) vis[x].resize(n, 0), dfs(x, x);
        if(vis[y].empty()) vis[y].resize(n, 0), dfs(y, y);
        if(vis[x][y]) return 1;
        if(vis[y][x]) return -1;
        return 0;
    }
    return pos[x]<pos[y] ? 1 : -1;
}

• Subtask 1: 5 / 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