oj.uz

Submission #433656

# Submission time Handle Problem Language Result Execution time Memory
433656 2021-06-20T09:16:53 Z usachevd0 Comparing Plants (IOI20_plants) C++17
5 / 100
 981 ms 45892 KB 
#include <bits/stdc++.h>
#include "plants.h"

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
    return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
    return y > x ? (x = y, true) : false;
}
void debug_out() {
    cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
    cerr << ' ' << A;
    debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
    for (int i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}
#ifdef LOCAL
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
    for (auto& e : v)
        stream << e << ' ';
    return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << ' ' << p.second;
}


const int INF32 = 1e9;
const int maxN = 2e5 + 5;
const int logN = 18;
int n, k;
int r[maxN];
int p[maxN];
int L[logN][maxN], R[logN][maxN];

int md(int x) {
    if ((x %= n) < 0)
        x += n;
    return x;
}

bool between(int l, int m, int r) {
    if (l <= r)
        return l <= m && m <= r;
    return m >= l || m <= r;
}

struct sgt {
    static const int N = 1 << logN;
    int mn[2 * N], lazy[2 * N];

    void apply(int v, int d) {
        mn[v] += d;
        lazy[v] += d;
    }

    void push(int v) {
        if (!lazy[v] || v >= N) return;
        apply(v << 1, lazy[v]);
        apply(v << 1 | 1, lazy[v]);
        lazy[v] = 0;
    }

    void upd(int v) {
        mn[v] = min(mn[v << 1], mn[v << 1 | 1]);
    }

    void build(int* a) {
        memset(mn, 0x3f, sizeof mn);
        memset(lazy, 0, sizeof lazy);
        for (int i = 0; i < n; ++i)
            mn[i + N] = a[i];
        for (int v = N - 1; v >= 1; --v)
            upd(v);
    }

    void disable(int v, int vl, int vr, int i) {
        if (vl == vr) {
            mn[v] = +INF32;
            return;
        }
        int vm = (vl + vr) >> 1;
        push(v);
        if (i <= vm)
            disable(v << 1, vl, vm, i);
        else
            disable(v << 1 | 1, vm + 1, vr, i);
        upd(v);
    }

    void add(int v, int vl, int vr, int l, int r, int delta) {
        if (l > r || vr < l || r < vl) return;
        if (l <= vl && vr <= r) {
            apply(v, delta);
            return;
        }
        int vm = (vl + vr) >> 1;
        push(v);
        add(v << 1, vl, vm, l, r, delta);
        add(v << 1 | 1, vm + 1, vr, l, r, delta);
        upd(v);
    }
    void add(int l, int r, int delta) {
        // cerr << "add " << (this) << ' ' << l << ' ' << r << ' ' << delta << endl;
        if (l <= r)
            add(1, 0, N - 1, l, r, delta);
        else {
            add(1, 0, N - 1, 0, r, delta);
            add(1, 0, N - 1, l, n - 1, delta);
        }
    }

    int GetFirstZero(int v, int vl, int vr, int l, int r, int x = 0) {
        if (l > r || vr < l || r < vl || mn[v] > x) return -1;
        if (vl == vr) return vl;
        int vm = (vl + vr) >> 1;
        push(v);
        int ansL = GetFirstZero(v << 1, vl, vm, l, r, x);
        if (ansL != -1)
            return ansL;
        return GetFirstZero(v << 1 | 1, vm + 1, vr, l, r, x);
    }
    int GetFirstZero(int l, int r, int x = 0) {
        if (l <= r)
            return GetFirstZero(1, 0, N - 1, l, r, x);
        else {
            int ans = GetFirstZero(1, 0, N - 1, l, n - 1);
            if (ans != -1)
                return ans;
            return GetFirstZero(1, 0, N - 1, 0, r);
        }
    }

    int GetMin(int v, int vl, int vr, int l, int r) {
        if (l > r || vr < l || r < vl) return +INF32;
        if (l <= vl && vr <= r) return mn[v];
        int vm = (vl + vr) >> 1;
        push(v);
        return min(GetMin(v << 1, vl, vm, l, r), GetMin(v << 1 | 1, vm + 1, vr, l, r));
    }
    int GetMin(int l, int r) {
        if (l <= r)
            return GetMin(1, 0, N - 1, l, r);
        return min(GetMin(1, 0, N - 1, l, n - 1), GetMin(1, 0, N - 1, 0, r));
    }

    void mdf(int v, int vl, int vr, int i, int val) {
        if (vl == vr) {
            mn[v] = val;
            return;
        }
        int vm = (vl + vr) >> 1;
        push(v);
        if (i <= vm)
            mdf(v << 1, vl, vm, i, val);
        else
            mdf(v << 1 | 1, vm + 1, vr, i, val);
        upd(v);
    }

    int gt(int v, int vl, int vr, int i) {
        if (vl == vr) return mn[v];
        int vm = (vl + vr) >> 1;
        push(v);
        if (i <= vm)
            return gt(v << 1, vl, vm, i);
        else
            return gt(v << 1 | 1, vm + 1, vr, i);
    }
} sr, sf;

void init(int _k, vector<int> _r) {
    n = _r.size(), k = _k;
    for (int i = 0; i < n; ++i)
        r[i] = _r[i];
    sr.build(r);
    sf.build(r);
    auto travelRZero = [&]() {
        for (int i = sr.GetFirstZero(1, 0, sr.N - 1, 0, n - 1); i != -1; i = sr.GetFirstZero(1, 0, sr.N - 1, 0, n - 1)) {
            sf.add(md(i + 1), md(i + k - 1), +1);
            sr.disable(1, 0, sr.N - 1, i);
        }
    };
    travelRZero();
    for (int v = 0; v < n; ++v) {
        int i = sf.GetFirstZero(1, 0, sf.N - 1, 0, n - 1);
        sf.disable(1, 0, sf.N - 1, i);
        sf.add(md(i + 1), md(i + k - 1), -1);
        sf.add(md(i - k + 1), md(i - 1), -1);
        sr.add(md(i - k + 1), md(i - 1), -1);
        travelRZero();
        p[i] = v;
    }

    for (int i = 0; i < n; ++i)
        sf.mdf(1, 0, sf.N - 1, i, +INF32);
    vector<int> ord(n);
    for (int i = 0; i < n; ++i)
        ord[p[i]] = i;
    memset(L, 255, sizeof L);
    memset(R, 255, sizeof R);
    reverse(all(ord));
    for (int i : ord) {
        int minL = sf.GetMin(md(i - k + 1), md(i - 1));
        if (minL < INF32 / 2)
            L[0][i] = sf.GetFirstZero(md(i - k + 1), md(i - 1), minL);
        int minR = sf.GetMin(md(i + 1), md(i + k - 1));
        if (minR < INF32 / 2)
            R[0][i] = sf.GetFirstZero(md(i + 1), md(i + k - 1), minR);
        // debug(L[0][i], i, R[0][i]);
        sf.mdf(1, 0, sf.N - 1, i, p[i]);
    }
    for (int j = 1; j < logN; ++j) {
        for (int i = 0; i < n; ++i) {
            if (L[j - 1][i] != -1 && L[j - 1][L[j - 1][i]] != -1 && between(L[j - 1][L[j - 1][i]], L[j - 1][i], i))
                L[j][i] = L[j - 1][L[j - 1][i]];
            if (R[j - 1][i] != -1 && R[j - 1][R[j - 1][i]] != -1 && between(i, R[j - 1][i], R[j - 1][R[j - 1][i]]))
                R[j][i] = R[j - 1][R[j - 1][i]];
        }
    }
}

bool Less(int x, int y) {
    {
        int i = x;
        for (int j = logN - 1; j >= 0; --j)
            if (L[j][i] != -1 && !between(L[j][i], y, x)) {
                i = L[j][i];
            }
        i = L[0][i];
        if (i != -1 && between(i, y, x) && p[i] <= p[y])
            return 1;
    }
    {
        int i = x;
        for (int j = logN - 1; j >= 0; --j)
            if (R[j][i] != -1 && !between(x, y, R[j][i]))
                i = R[j][i];
        i = R[0][i];
        if (i != -1 && between(x, y, i) && p[i] <= p[y])
            return 1;
    }
    return 0;
}

int compare_plants(int x, int y) {
    if (Less(x, y))
        return 1;
    if (Less(y, x))
        return -1;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 36684 KB Output is correct
2 Correct 20 ms 36592 KB Output is correct
3 Correct 20 ms 36588 KB Output is correct
4 Correct 23 ms 36620 KB Output is correct
5 Correct 20 ms 36684 KB Output is correct
6 Correct 115 ms 40476 KB Output is correct
7 Correct 230 ms 41952 KB Output is correct
8 Correct 744 ms 45764 KB Output is correct
9 Correct 800 ms 45800 KB Output is correct
10 Correct 869 ms 45856 KB Output is correct
11 Correct 880 ms 45752 KB Output is correct
12 Correct 862 ms 45852 KB Output is correct
13 Correct 877 ms 45892 KB Output is correct
14 Correct 981 ms 45764 KB Output is correct

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 36672 KB Output is correct
2 Incorrect 19 ms 36576 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 36684 KB Output is correct
2 Correct 18 ms 36672 KB Output is correct
3 Correct 18 ms 36684 KB Output is correct
4 Incorrect 19 ms 36684 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 36648 KB Output is correct
2 Correct 18 ms 36580 KB Output is correct
3 Correct 18 ms 36684 KB Output is correct
4 Correct 20 ms 36684 KB Output is correct
5 Incorrect 26 ms 36608 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 36684 KB Output is correct
2 Correct 20 ms 36592 KB Output is correct
3 Correct 20 ms 36588 KB Output is correct
4 Correct 23 ms 36620 KB Output is correct
5 Correct 20 ms 36684 KB Output is correct
6 Correct 115 ms 40476 KB Output is correct
7 Correct 230 ms 41952 KB Output is correct
8 Correct 744 ms 45764 KB Output is correct
9 Correct 800 ms 45800 KB Output is correct
10 Correct 869 ms 45856 KB Output is correct
11 Correct 880 ms 45752 KB Output is correct
12 Correct 862 ms 45852 KB Output is correct
13 Correct 877 ms 45892 KB Output is correct
14 Correct 981 ms 45764 KB Output is correct
15 Correct 18 ms 36684 KB Output is correct
16 Correct 18 ms 36664 KB Output is correct
17 Incorrect 18 ms 36632 KB Output isn't correct
18 Halted 0 ms 0 KB -