oj.uz

답안 #433660

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
433660 2021-06-20T09:18:05 Z usachevd0 식물 비교 (IOI20_plants) C++17
5 / 100
 963 ms 42964 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)
                L[j][i] = L[j - 1][L[j - 1][i]];
            if (R[j - 1][i] != -1 && R[j - 1][R[j - 1][i]] != -1)
                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

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 36648 KB Output is correct
2 Correct 21 ms 36604 KB Output is correct
3 Correct 21 ms 36700 KB Output is correct
4 Correct 18 ms 36684 KB Output is correct
5 Correct 18 ms 36600 KB Output is correct
6 Correct 101 ms 39388 KB Output is correct
7 Correct 186 ms 39756 KB Output is correct
8 Correct 727 ms 42960 KB Output is correct
9 Correct 765 ms 42964 KB Output is correct
10 Correct 866 ms 42820 KB Output is correct
11 Correct 826 ms 42860 KB Output is correct
12 Correct 836 ms 42852 KB Output is correct
13 Correct 876 ms 42944 KB Output is correct
14 Correct 963 ms 42856 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 36684 KB Output is correct
2 Correct 18 ms 36620 KB Output is correct
3 Incorrect 17 ms 36588 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 36684 KB Output is correct
2 Correct 18 ms 36620 KB Output is correct
3 Incorrect 17 ms 36588 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 36684 KB Output is correct
2 Incorrect 18 ms 36596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 36608 KB Output is correct
2 Correct 18 ms 36684 KB Output is correct
3 Correct 20 ms 36644 KB Output is correct
4 Incorrect 19 ms 36692 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 36668 KB Output is correct
2 Correct 18 ms 36624 KB Output is correct
3 Correct 19 ms 36684 KB Output is correct
4 Correct 18 ms 36692 KB Output is correct
5 Incorrect 21 ms 36636 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 36648 KB Output is correct
2 Correct 21 ms 36604 KB Output is correct
3 Correct 21 ms 36700 KB Output is correct
4 Correct 18 ms 36684 KB Output is correct
5 Correct 18 ms 36600 KB Output is correct
6 Correct 101 ms 39388 KB Output is correct
7 Correct 186 ms 39756 KB Output is correct
8 Correct 727 ms 42960 KB Output is correct
9 Correct 765 ms 42964 KB Output is correct
10 Correct 866 ms 42820 KB Output is correct
11 Correct 826 ms 42860 KB Output is correct
12 Correct 836 ms 42852 KB Output is correct
13 Correct 876 ms 42944 KB Output is correct
14 Correct 963 ms 42856 KB Output is correct
15 Correct 18 ms 36684 KB Output is correct
16 Correct 18 ms 36620 KB Output is correct
17 Incorrect 17 ms 36588 KB Output isn't correct
18 Halted 0 ms 0 KB -