oj.uz

Submission #410120

# Submission time Handle Problem Language Result Execution time Memory
410120 2021-05-22T04:02:57 Z 534351 Comparing Plants (IOI20_plants) C++17
5 / 100
 107 ms 14152 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 6 ms 4960 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 73 ms 8772 KB Output is correct
7 Correct 70 ms 10372 KB Output is correct
8 Correct 100 ms 14096 KB Output is correct
9 Correct 97 ms 14152 KB Output is correct
10 Correct 95 ms 14148 KB Output is correct
11 Correct 94 ms 14112 KB Output is correct
12 Correct 93 ms 14148 KB Output is correct
13 Correct 104 ms 14148 KB Output is correct
14 Correct 107 ms 14096 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 6 ms 4940 KB Output is correct
3 Incorrect 6 ms 4940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 6 ms 4940 KB Output is correct
3 Incorrect 6 ms 4940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5000 KB Output is correct
2 Incorrect 6 ms 4912 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 6 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Incorrect 6 ms 4940 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 6 ms 4940 KB Output is correct
3 Correct 7 ms 4940 KB Output is correct
4 Incorrect 4 ms 5004 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 6 ms 4960 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 73 ms 8772 KB Output is correct
7 Correct 70 ms 10372 KB Output is correct
8 Correct 100 ms 14096 KB Output is correct
9 Correct 97 ms 14152 KB Output is correct
10 Correct 95 ms 14148 KB Output is correct
11 Correct 94 ms 14112 KB Output is correct
12 Correct 93 ms 14148 KB Output is correct
13 Correct 104 ms 14148 KB Output is correct
14 Correct 107 ms 14096 KB Output is correct
15 Correct 4 ms 4940 KB Output is correct
16 Correct 6 ms 4940 KB Output is correct
17 Incorrect 6 ms 4940 KB Output isn't correct
18 Halted 0 ms 0 KB -