oj.uz

Submission #434208

# Submission time Handle Problem Language Result Execution time Memory
434208 2021-06-20T18:16:35 Z usachevd0 Comparing Plants (IOI20_plants) C++14
100 / 100
 1581 ms 71036 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);
    // mdebug(p, n);
    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] = md(i - L[0][i]);
        } else {
            L[0][i] = -1;
            LD[0][i] = +INF32;
        }
        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] = md(R[0][i] - i);
        } else {
            R[0][i] = -1;
            RD[0][i] = +INF32;
        }
        // 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) {
    // debug(x, y);
    {
        int i = x;
        int dxy = md(x - y);
        for (int j = logN - 1, d = 0; j >= 0; --j)
            if (L[j][i] != -1 && d + LD[j][i] < dxy) {
                d += LD[j][i];
                i = L[j][i];
            }
        i = L[0][i];
        if (i != -1 && between(i, y, x) && p[i] <= p[y])
            return 1;
    }
    {
        int i = x;
        int dxy = md(y - x);
        for (int j = logN - 1, d = 0; j >= 0; --j)
            if (R[j][i] != -1 && d + RD[j][i] < dxy) {
                d += RD[j][i];
                i = R[j][i];
            }
        i = R[0][i];
        if (i != -1 && between(x, y, i) && p[i] <= p[y])
            return 1;
    }
    // exit(0);
    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 21 ms 36684 KB Output is correct
2 Correct 21 ms 36700 KB Output is correct
3 Correct 22 ms 36704 KB Output is correct
4 Correct 23 ms 36684 KB Output is correct
5 Correct 20 ms 36672 KB Output is correct
6 Correct 113 ms 40528 KB Output is correct
7 Correct 211 ms 43528 KB Output is correct
8 Correct 737 ms 56776 KB Output is correct
9 Correct 798 ms 60612 KB Output is correct
10 Correct 852 ms 60336 KB Output is correct
11 Correct 883 ms 58560 KB Output is correct
12 Correct 891 ms 59660 KB Output is correct
13 Correct 904 ms 60300 KB Output is correct
14 Correct 973 ms 60208 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 36684 KB Output is correct
2 Correct 20 ms 36656 KB Output is correct
3 Correct 20 ms 36724 KB Output is correct
4 Correct 19 ms 36684 KB Output is correct
5 Correct 19 ms 36696 KB Output is correct
6 Correct 27 ms 36824 KB Output is correct
7 Correct 134 ms 41668 KB Output is correct
8 Correct 22 ms 36812 KB Output is correct
9 Correct 29 ms 36836 KB Output is correct
10 Correct 138 ms 41680 KB Output is correct
11 Correct 137 ms 41796 KB Output is correct
12 Correct 174 ms 41924 KB Output is correct
13 Correct 139 ms 41704 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 36684 KB Output is correct
2 Correct 20 ms 36656 KB Output is correct
3 Correct 20 ms 36724 KB Output is correct
4 Correct 19 ms 36684 KB Output is correct
5 Correct 19 ms 36696 KB Output is correct
6 Correct 27 ms 36824 KB Output is correct
7 Correct 134 ms 41668 KB Output is correct
8 Correct 22 ms 36812 KB Output is correct
9 Correct 29 ms 36836 KB Output is correct
10 Correct 138 ms 41680 KB Output is correct
11 Correct 137 ms 41796 KB Output is correct
12 Correct 174 ms 41924 KB Output is correct
13 Correct 139 ms 41704 KB Output is correct
14 Correct 219 ms 42876 KB Output is correct
15 Correct 1526 ms 53932 KB Output is correct
16 Correct 231 ms 43240 KB Output is correct
17 Correct 1566 ms 55968 KB Output is correct
18 Correct 1125 ms 60628 KB Output is correct
19 Correct 1298 ms 61088 KB Output is correct
20 Correct 1498 ms 52932 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 36684 KB Output is correct
2 Correct 19 ms 36684 KB Output is correct
3 Correct 136 ms 41504 KB Output is correct
4 Correct 1144 ms 71036 KB Output is correct
5 Correct 1251 ms 68352 KB Output is correct
6 Correct 1557 ms 64492 KB Output is correct
7 Correct 1461 ms 60552 KB Output is correct
8 Correct 1493 ms 56016 KB Output is correct
9 Correct 1050 ms 61764 KB Output is correct
10 Correct 1162 ms 68600 KB Output is correct
11 Correct 891 ms 60304 KB Output is correct
12 Correct 1052 ms 60392 KB Output is correct
13 Correct 1111 ms 60480 KB Output is correct

Subtask #5
11.0 / 11.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 36696 KB Output is correct
4 Correct 19 ms 36656 KB Output is correct
5 Correct 19 ms 36640 KB Output is correct
6 Correct 19 ms 36812 KB Output is correct
7 Correct 41 ms 37628 KB Output is correct
8 Correct 37 ms 37700 KB Output is correct
9 Correct 44 ms 37688 KB Output is correct
10 Correct 39 ms 37632 KB Output is correct
11 Correct 42 ms 37676 KB Output is correct
12 Correct 42 ms 37692 KB Output is correct
13 Correct 37 ms 37660 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 36704 KB Output is correct
2 Correct 18 ms 36684 KB Output is correct
3 Correct 18 ms 36700 KB Output is correct
4 Correct 18 ms 36684 KB Output is correct
5 Correct 21 ms 36812 KB Output is correct
6 Correct 970 ms 57704 KB Output is correct
7 Correct 1154 ms 61052 KB Output is correct
8 Correct 1196 ms 56608 KB Output is correct
9 Correct 1416 ms 53576 KB Output is correct
10 Correct 881 ms 60760 KB Output is correct
11 Correct 1069 ms 60352 KB Output is correct
12 Correct 895 ms 70060 KB Output is correct
13 Correct 1076 ms 67652 KB Output is correct
14 Correct 1107 ms 63816 KB Output is correct
15 Correct 1348 ms 59848 KB Output is correct
16 Correct 769 ms 68428 KB Output is correct
17 Correct 914 ms 63576 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 36684 KB Output is correct
2 Correct 21 ms 36700 KB Output is correct
3 Correct 22 ms 36704 KB Output is correct
4 Correct 23 ms 36684 KB Output is correct
5 Correct 20 ms 36672 KB Output is correct
6 Correct 113 ms 40528 KB Output is correct
7 Correct 211 ms 43528 KB Output is correct
8 Correct 737 ms 56776 KB Output is correct
9 Correct 798 ms 60612 KB Output is correct
10 Correct 852 ms 60336 KB Output is correct
11 Correct 883 ms 58560 KB Output is correct
12 Correct 891 ms 59660 KB Output is correct
13 Correct 904 ms 60300 KB Output is correct
14 Correct 973 ms 60208 KB Output is correct
15 Correct 24 ms 36684 KB Output is correct
16 Correct 20 ms 36656 KB Output is correct
17 Correct 20 ms 36724 KB Output is correct
18 Correct 19 ms 36684 KB Output is correct
19 Correct 19 ms 36696 KB Output is correct
20 Correct 27 ms 36824 KB Output is correct
21 Correct 134 ms 41668 KB Output is correct
22 Correct 22 ms 36812 KB Output is correct
23 Correct 29 ms 36836 KB Output is correct
24 Correct 138 ms 41680 KB Output is correct
25 Correct 137 ms 41796 KB Output is correct
26 Correct 174 ms 41924 KB Output is correct
27 Correct 139 ms 41704 KB Output is correct
28 Correct 219 ms 42876 KB Output is correct
29 Correct 1526 ms 53932 KB Output is correct
30 Correct 231 ms 43240 KB Output is correct
31 Correct 1566 ms 55968 KB Output is correct
32 Correct 1125 ms 60628 KB Output is correct
33 Correct 1298 ms 61088 KB Output is correct
34 Correct 1498 ms 52932 KB Output is correct
35 Correct 18 ms 36684 KB Output is correct
36 Correct 19 ms 36684 KB Output is correct
37 Correct 136 ms 41504 KB Output is correct
38 Correct 1144 ms 71036 KB Output is correct
39 Correct 1251 ms 68352 KB Output is correct
40 Correct 1557 ms 64492 KB Output is correct
41 Correct 1461 ms 60552 KB Output is correct
42 Correct 1493 ms 56016 KB Output is correct
43 Correct 1050 ms 61764 KB Output is correct
44 Correct 1162 ms 68600 KB Output is correct
45 Correct 891 ms 60304 KB Output is correct
46 Correct 1052 ms 60392 KB Output is correct
47 Correct 1111 ms 60480 KB Output is correct
48 Correct 18 ms 36684 KB Output is correct
49 Correct 18 ms 36684 KB Output is correct
50 Correct 18 ms 36696 KB Output is correct
51 Correct 19 ms 36656 KB Output is correct
52 Correct 19 ms 36640 KB Output is correct
53 Correct 19 ms 36812 KB Output is correct
54 Correct 41 ms 37628 KB Output is correct
55 Correct 37 ms 37700 KB Output is correct
56 Correct 44 ms 37688 KB Output is correct
57 Correct 39 ms 37632 KB Output is correct
58 Correct 42 ms 37676 KB Output is correct
59 Correct 42 ms 37692 KB Output is correct
60 Correct 37 ms 37660 KB Output is correct
61 Correct 130 ms 41304 KB Output is correct
62 Correct 201 ms 42872 KB Output is correct
63 Correct 949 ms 55004 KB Output is correct
64 Correct 1214 ms 58580 KB Output is correct
65 Correct 1503 ms 61932 KB Output is correct
66 Correct 1516 ms 57376 KB Output is correct
67 Correct 1581 ms 54420 KB Output is correct
68 Correct 1113 ms 61940 KB Output is correct
69 Correct 1323 ms 61236 KB Output is correct
70 Correct 1134 ms 71000 KB Output is correct
71 Correct 1467 ms 68648 KB Output is correct
72 Correct 1490 ms 64512 KB Output is correct
73 Correct 1519 ms 60472 KB Output is correct
74 Correct 971 ms 55620 KB Output is correct
75 Correct 1205 ms 65896 KB Output is correct