Submission #1063224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063224		c2zi6	Comparing Plants (IOI20_plants)	C++14	25 / 100	4075 ms	27448 KiB

plants

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "plants.h"

struct MINARGSEGTREE {
    int n;
    VPI tree;
    VI lazy;
    MINARGSEGTREE(){}
    MINARGSEGTREE(int sz) {
        n = 1;
        while (n < sz) n *= 2;
        tree = VPI(2*n, {+1e9, -1});
        lazy = VI(2*n);
    }
    void push(int N) {
        tree[N].ff += lazy[N];
        if (2*N+2 < 2*n) {
            lazy[2*N+1] += lazy[N];
            lazy[2*N+2] += lazy[N];
        }
        lazy[N] = 0;
    }
    void set(int N, int L, int R, int i, PII s) {
        push(N);
        if (i < L || i > R) return;
        if (L == R) {
            tree[N] = s;
            return;
        }
        int M = (L + R) / 2;
        set(2*N+1, L, M, i, s);
        set(2*N+2, M+1, R, i, s);
        tree[N] = min(tree[2*N+1], tree[2*N+2]);
    }
    void add(int N, int L, int R, int l, int r, int s) {
        push(N);
        if (R < l || L > r) return;
        if (l <= L && R <= r) {
            lazy[N] = s;
            push(N);
            return;
        }
        int M = (L + R) / 2;
        add(2*N+1, L, M, l, r, s);
        add(2*N+2, M+1, R, l, r, s);
        tree[N] = min(tree[2*N+1], tree[2*N+2]);
    }
    PII get(int N, int L, int R, int l, int r) {
        push(N);
        if (l <= L && R <= r) return tree[N];
        if (R < l || L > r) return {+1e9, -1};
        int M = (L + R) / 2;
        return min(get(2*N+1, L, M, l, r), get(2*N+2, M+1, R, l, r));
    }
    void set(int i, int s) {
        set(0, 0, n-1, i, {s, i});
    }
    void add(int l, int r, int s) {
        add(0, 0, n-1, l, r, s);
    }
    PII get(int l, int r) {
        return get(0, 0, n-1, l, r);
    }
};
struct FIRSTZERODS {
    int n;
    MINARGSEGTREE seg;
    FIRSTZERODS(){}
    FIRSTZERODS(VI a) {
        n = a.size();
        seg = MINARGSEGTREE(n);
        rep(i, n) seg.set(i, a[i]);
    }
    void remove(int i) {
        seg.set(i, +1e9);
    }
    void decrement(int l, int r) {
        l = (l+100*n)%n;
        r = (r+100*n)%n;
        if (l <= r) seg.add(l, r, -1);
        else {
            seg.add(l, n-1, -1);
            seg.add(0, r, -1);
        }
    }
    int get(int l, int r) {
        l = (l+100*n)%n;
        r = (r+100*n)%n;
        PII ret;
        if (l <= r) ret = seg.get(l, r);
        else {
            ret = seg.get(l, n-1);
            if (ret.ff) ret = seg.get(0, r);
        }
        if (ret.ff == 0) return ret.ss;
        return -1;
    }
    void print() {
        rep(i, n) cout << seg.get(i, i).ff << " "; cout << endl;
    }
};

int n, k;
FIRSTZERODS seg;
VI a;
int mx;

VVI gp;

void extract(int i) {
    while (true) {
        int prev = seg.get(i-k+1, i-1);
        if (prev == -1) break;
        extract(prev);
    }
    a[i] = mx--;
    seg.remove(i);
    seg.decrement(i-k+1, i-1);
}

VI b;
VI pr, pl;

void init(int K_ARG, VI r) {
    k = K_ARG;
    n = r.size();
    seg = FIRSTZERODS(r);
    a = VI(n, -1);
    mx = n-1;
    while (mx >= 0) extract(seg.get(0, n-1));

    if (n <= 300) {
        gp = VVI(n, VI(n));
        rep(i, n) replr(jwm, i+1, i+k-1) {
            int j = jwm%n;
            if (a[j] > a[i]) gp[i][j] = true;
            else gp[j][i] = true;
        }
        rep(m, n) rep(u, n) rep(v, n) {
            gp[u][v] |= gp[u][m] && gp[m][v];
        }
    }
    rep(_, 3) for (int x : a) b.pb(x);
    pr = pl = VI(3*n);
    rep(i, 3*n) pr[i] = pl[i] = i;

    set<PII> st;
    replr(i, 0, k-1) st.insert({b[i], i});
    replr(i, 0, 3*n-1) {
        auto it = st.upper_bound({b[i], +2e9});
        if (it != st.end()) pr[i] = it->ss;
        st.erase({b[i], i});
        if (i+k < 3*n) st.insert({b[i+k], i+k});
    }
    st = set<PII>();
    reprl(i, 3*n-1, 3*n-k) st.insert({b[i], i});
    reprl(i, 3*n-1, 0) {
        auto it = st.upper_bound({b[i], +2e9});
        if (it != st.end()) pl[i] = it->ss;
        st.erase({b[i], i});
        if (i-k >= 0) st.insert({b[i-k], i-k});
    }

    /*rep(i, 3*n) cout << i << "\t"; cout << endl;*/
    /*for (int x : b) cout << x <<  " "; cout << endl;*/
    /*for (int x : pr) cout << x << " "; cout << endl;*/
    /*for (int x : pl) cout << x << " "; cout << endl;*/
}

bool goright(int x, int y) {
    while (pr[x] < y) {
        if (x == pr[x]) break;
        x = pr[x];
    }
    return y <= x+k-1 && b[y] > b[x];
}
bool goleft(int x, int y) {
    while (pl[x] > y) {
        if (x == pl[x]) break;
        x = pl[x];
    }
    return x <= y+k-1 && b[y] > b[x];
}
bool issmaller(int x, int y) {
    if (y > x) return goright(x, y) || goleft(x, y-n);
    return goright(x, y+n) || goleft(x, y);
}

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

int cp2(int x, int y) {
    if (gp[y][x]) return +1;
    if (gp[x][y]) return -1;
    return 0;
}

int compare_plants(int x, int y) {
    return cp1(x, y);
    /*cout << cp1(x, y) << " " << cp2(x, y) << endl;*/
    /*return -314;*/
    if (cp1(x, y) != cp2(x, y)) {
        rep(i, 200) cout << "VAX QU ";
        cout << endl;

        cout << x << " " << y << endl;
        abort();
    } else return cp2(x, y);

    if (n <= 300) {
    }
    if (a[x] > a[y]) return +1;
    if (a[x] < a[y]) return -1;
	return 0;
}

Compilation message (stderr)

plants.cpp: In member function 'void FIRSTZERODS::print()':
plants.cpp:9:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    9 | #define rep(i, n) for (int i = 0; i < int(n); ++i)
      |                   ^~~
plants.cpp:129:9: note: in expansion of macro 'rep'
  129 |         rep(i, n) cout << seg.get(i, i).ff << " "; cout << endl;
      |         ^~~
plants.cpp:129:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  129 |         rep(i, n) cout << seg.get(i, i).ff << " "; cout << endl;
      |                                                    ^~~~

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