oj.uz

Submission #433697

# Submission time Handle Problem Language Result Execution time Memory
433697 2021-06-20T09:37:38 Z usachevd0 Comparing Plants (IOI20_plants) C++17
5 / 100
 991 ms 57540 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 GetFirstLeq(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 = GetFirstLeq(v << 1, vl, vm, l, r, x);
        if (ansL != -1)
            return ansL;
        return GetFirstLeq(v << 1 | 1, vm + 1, vr, l, r, x);
    }
    int GetFirstLeq(int l, int r, int x = 0) {
        if (l <= r)
            return GetFirstLeq(1, 0, N - 1, l, r, x);
        else {
            int ans = GetFirstLeq(1, 0, N - 1, l, n - 1, x);
            if (ans != -1)
                return ans;
            return GetFirstLeq(1, 0, N - 1, 0, r, x);
        }
    }

    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.GetFirstLeq(1, 0, sr.N - 1, 0, n - 1); i != -1; i = sr.GetFirstLeq(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.GetFirstLeq(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.GetFirstLeq(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.GetFirstLeq(md(i + 1), md(i + k - 1), minR);
            RD[0][i] = dist(R[0][i], i);
        }
        // debug(L[0][i], i, R[0][i]);
        // debug(minL, minR);
        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_stu(int x, int y) {
    if (p[x] < p[y]) return 1;
    return -1;
}

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 20 ms 36684 KB Output is correct
2 Correct 22 ms 36728 KB Output is correct
3 Correct 22 ms 36664 KB Output is correct
4 Correct 19 ms 36664 KB Output is correct
5 Correct 22 ms 36684 KB Output is correct
6 Correct 126 ms 39520 KB Output is correct
7 Correct 232 ms 41372 KB Output is correct
8 Correct 713 ms 53844 KB Output is correct
9 Correct 821 ms 57540 KB Output is correct
10 Correct 884 ms 57196 KB Output is correct
11 Correct 894 ms 54904 KB Output is correct
12 Correct 910 ms 55820 KB Output is correct
13 Correct 939 ms 56576 KB Output is correct
14 Correct 991 ms 56468 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 36660 KB Output is correct
2 Correct 19 ms 36728 KB Output is correct
3 Correct 19 ms 36688 KB Output is correct
4 Correct 19 ms 36676 KB Output is correct
5 Incorrect 20 ms 36740 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 36660 KB Output is correct
2 Correct 19 ms 36728 KB Output is correct
3 Correct 19 ms 36688 KB Output is correct
4 Correct 19 ms 36676 KB Output is correct
5 Incorrect 20 ms 36740 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 36708 KB Output is correct
2 Correct 17 ms 36704 KB Output is correct
3 Incorrect 130 ms 39748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 36640 KB Output is correct
2 Correct 22 ms 36624 KB Output is correct
3 Correct 18 ms 36652 KB Output is correct
4 Correct 20 ms 36684 KB Output is correct
5 Correct 20 ms 36724 KB Output is correct
6 Correct 22 ms 36812 KB Output is correct
7 Correct 49 ms 37656 KB Output is correct
8 Incorrect 43 ms 37700 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 36708 KB Output is correct
2 Correct 19 ms 36660 KB Output is correct
3 Correct 19 ms 36684 KB Output is correct
4 Correct 19 ms 36620 KB Output is correct
5 Incorrect 23 ms 36788 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 36684 KB Output is correct
2 Correct 22 ms 36728 KB Output is correct
3 Correct 22 ms 36664 KB Output is correct
4 Correct 19 ms 36664 KB Output is correct
5 Correct 22 ms 36684 KB Output is correct
6 Correct 126 ms 39520 KB Output is correct
7 Correct 232 ms 41372 KB Output is correct
8 Correct 713 ms 53844 KB Output is correct
9 Correct 821 ms 57540 KB Output is correct
10 Correct 884 ms 57196 KB Output is correct
11 Correct 894 ms 54904 KB Output is correct
12 Correct 910 ms 55820 KB Output is correct
13 Correct 939 ms 56576 KB Output is correct
14 Correct 991 ms 56468 KB Output is correct
15 Correct 19 ms 36660 KB Output is correct
16 Correct 19 ms 36728 KB Output is correct
17 Correct 19 ms 36688 KB Output is correct
18 Correct 19 ms 36676 KB Output is correct
19 Incorrect 20 ms 36740 KB Output isn't correct
20 Halted 0 ms 0 KB -