Submission #410120

#	Time	Username	Problem	Language	Result	Execution time	Memory
410120		534351	Comparing Plants (IOI20_plants)	C++17	5 / 100	107 ms	14152 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int) (x).size())

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

const int MAXN = 2e5 + 13;
const int INF = 1e9 + 7;

int N, K;
int arr[MAXN];
int val[MAXN];
pii seg[3 * MAXN];
int lazy[3 * MAXN];
vi edge[MAXN];
int pref[2][MAXN];

void build(int w, int L, int R)
{
    if (L == R)
    {
        seg[w] = {arr[L], L};
        return;
    }
    int mid = (L + R) >> 1;
    build(w << 1, L, mid);
    build(w << 1 | 1, mid + 1, R);
    seg[w] = min(seg[w << 1], seg[w << 1 | 1]);
}
void push(int w, int L, int R)
{
    if (lazy[w] == 0)
    {
        return;
    }
    seg[w].fi += lazy[w];
    if (L != R)
    {
        lazy[w << 1] += lazy[w];
        lazy[w << 1 | 1] += lazy[w];
    }
    lazy[w] = 0;
    return;
}
void update(int w, int L, int R, int a, int b, int v)
{
    push(w, L, R);
    if (b < L || R < a) return;
    if (a <= L && R <= b)
    {
        lazy[w] += v;
        push(w, L, R);
        return;
    }
    int mid = (L + R) >> 1;
    update(w << 1, L, mid, a, b, v);
    update(w << 1 | 1, mid + 1, R, a, b, v);
    seg[w] = min(seg[w << 1], seg[w << 1 | 1]);
}
pii query(int w, int L, int R, int a, int b)
{
    push(w, L, R);
    if (a <= L && R <= b)
    {
        return seg[w];
    }
    int mid = (L + R) >> 1;
    if (b <= mid) return query(w << 1, L, mid, a, b);
    if (mid < a) return query(w << 1 | 1, mid + 1, R, a, b);
    return min(query(w << 1, L, mid, a, b), query(w << 1 | 1, mid + 1, R, a, b));
}

vpi getchild(int u)
{
    vpi res;
    pii p = {u + 1, u + K};
    if (p.se < N)
    {
        res.PB(p);
    }
    else
    {
        res.PB({p.fi, N - 1});
        res.PB({0, p.se - N});
    }
    return res;
}
vpi getparent(int u)
{
    vpi res;
    pii p = {u - K, u - 1};
    if (p.fi >= 0)
    {
        res.PB(p);
    }
    else
    {
        res.PB({0, u - 1});
        res.PB({p.fi + N, N - 1});
    }
    return res;
}
pii ask(vpi v)
{
    pii res = query(1, 0, N - 1, v[0].fi, v[0].se);
    FOR(i, 1, SZ(v))
    {
        res = min(res, query(1, 0, N - 1, v[i].fi, v[i].se));
    }
    return res;
}

void init(int k, vi r)
{
	N = SZ(r);
    K = k; K--;
    FOR(i, 0, N)
    {
        arr[i] = r[i];
        pref[0][i + 1] = pref[0][i] + (arr[i] == 0);
        pref[1][i + 1] = pref[1][i] + (arr[i] == 1);
    }
    //find the 0. there can only be one of them. that # is N-1.
    //then subtract 1 from its chidlren.
    // build(1, 0, N - 1);
    // FORD(i, N, 0)
    // {
    //     auto p = query(1, 0, N - 1, 0, N - 1);
    //     val[p.se] = i;
    //     update(1, 0, N - 1, p.se, p.se, INF);
    //     vpi v = getparent(p.se);
    //     for (pii q : v)
    //     {
    //         update(1, 0, N - 1, q.fi, q.se, -1);
    //     }
    // }
    // FOR(i, 0, N)
    // {
    //     cerr << val[i] << endl;
    // }
}

int compare_plants(int x, int y)
{
    if (x > y)
    {
        return -compare_plants(y, x);
    }
    if (pref[0][y] - pref[0][x] == y - x)
    {
        return 1;
    }
    if (pref[1][y] - pref[1][x] == y - x)
    {
        return -1;
    }
    if (pref[0][N] - pref[0][y] + pref[0][x] == N - (y - x))
    {
        return -1;
    }
    if (pref[1][N] - pref[1][y] + pref[1][x] == N - (y - x))
    {
        return 1;
    }
    return 0;
    //their ranges must overlap??
    //if x...y-1 is all 0's then it's -1.
    //if x...y-1 is all 1's then it's 1.
    //if y...x-1 is all 0's then it's 1.
    //if y...x-1 is all 1's then it's -1.
    //check if there's a path from x -> y.

}

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