oj.uz

Submission #433666

# Submission time Handle Problem Language Result Execution time Memory
433666 2021-06-20T09:22:45 Z usachevd0 Comparing Plants (IOI20_plants) C++17
5 / 100
 985 ms 57752 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], LD[logN][maxN], R[logN][maxN], RD[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;
}

int dist(int i, int j) {
    return min({j - i, i + n - j, j + n - i});
}

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);
            LD[0][i] = dist(L[0][i], i);
        }
        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);
            RD[0][i] = dist(R[0][i], i);
        }
        // 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) {
                int l = L[j - 1][i];
                if (LD[j - 1][i] + LD[j - 1][l] < n) {
                    L[j][i] = L[j - 1][l];
                    LD[j][i] = LD[j - 1][i] + LD[j - 1][l];
                }
            }
            if (R[j - 1][i] != -1) {
                int r = R[j - 1][i];
                if (RD[j - 1][i] + RD[j - 1][r] < n) {
                    R[j][i] = R[j - 1][r];
                    RD[j][i] = RD[j - 1][i] + RD[j - 1][r];
                }
            }
        }
    }
}

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 18 ms 36688 KB Output is correct
3 Correct 19 ms 36684 KB Output is correct
4 Correct 18 ms 36728 KB Output is correct
5 Correct 19 ms 36632 KB Output is correct
6 Correct 94 ms 39528 KB Output is correct
7 Correct 192 ms 41384 KB Output is correct
8 Correct 710 ms 53872 KB Output is correct
9 Correct 792 ms 57752 KB Output is correct
10 Correct 844 ms 57164 KB Output is correct
11 Correct 890 ms 54828 KB Output is correct
12 Correct 917 ms 55944 KB Output is correct
13 Correct 898 ms 56524 KB Output is correct
14 Correct 985 ms 56536 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 36684 KB Output is correct
3 Incorrect 18 ms 36704 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 36684 KB Output is correct
3 Incorrect 18 ms 36704 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 36684 KB Output is correct
2 Incorrect 18 ms 36684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 36732 KB Output is correct
2 Correct 18 ms 36684 KB Output is correct
3 Correct 18 ms 36620 KB Output is correct
4 Incorrect 18 ms 36656 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 36684 KB Output is correct
2 Correct 18 ms 36684 KB Output is correct
3 Correct 18 ms 36676 KB Output is correct
4 Correct 19 ms 36732 KB Output is correct
5 Incorrect 22 ms 36808 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 18 ms 36688 KB Output is correct
3 Correct 19 ms 36684 KB Output is correct
4 Correct 18 ms 36728 KB Output is correct
5 Correct 19 ms 36632 KB Output is correct
6 Correct 94 ms 39528 KB Output is correct
7 Correct 192 ms 41384 KB Output is correct
8 Correct 710 ms 53872 KB Output is correct
9 Correct 792 ms 57752 KB Output is correct
10 Correct 844 ms 57164 KB Output is correct
11 Correct 890 ms 54828 KB Output is correct
12 Correct 917 ms 55944 KB Output is correct
13 Correct 898 ms 56524 KB Output is correct
14 Correct 985 ms 56536 KB Output is correct
15 Correct 18 ms 36684 KB Output is correct
16 Correct 18 ms 36684 KB Output is correct
17 Incorrect 18 ms 36704 KB Output isn't correct
18 Halted 0 ms 0 KB -