oj.uz

Submission #410070

# Submission time Handle Problem Language Result Execution time Memory
410070 2021-05-22T00:06:46 Z 534351 Comparing Plants (IOI20_plants) C++17
0 / 100
 72 ms 4944 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];

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];
    }
    //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;
        vpi v = getparent(p.se);
        update(1, 0, N - 1, p.se, p.se, INF);
        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)
{
    return (val[x] < val[y] ? -1 : 1);
    //check if there's a path from x -> y.
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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