oj.uz

Submission #433628

# Submission time Handle Problem Language Result Execution time Memory
433628 2021-06-20T08:47:52 Z usachevd0 Comparing Plants (IOI20_plants) C++17
44 / 100
 1056 ms 17648 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 md(int x) {
    if ((x %= n) < 0)
        x += n;
    return x;
}

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) {
        if (l > r || vr < l || r < vl || mn[v] > 0) return -1;
        if (vl == vr) return vl;
        int vm = (vl + vr) >> 1;
        push(v);
        int ansL = GetFirstZero(v << 1, vl, vm, l, r);
        if (ansL != -1)
            return ansL;
        return GetFirstZero(v << 1 | 1, vm + 1, vr, l, r);
    }

    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) {
    //     cerr << "r: ";
    //     for (int i = 0; i < n; ++i)
    //         cerr << sr.gt(1, 0, sr.N - 1, i) << ' ';
    //     cerr << endl;
    //     cerr << "f: ";
    //     for (int i = 0; i < n; ++i)
    //         cerr << sf.gt(1, 0, sf.N - 1, i) << ' ';
    //     cerr << endl;
        int i = sf.GetFirstZero(1, 0, sf.N - 1, 0, n - 1);
        // assert(sf.GetFirstZero(1, 0, sf.N - 1, i + 1, n - 1) == -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;
    }
}

int compare_plants(int x, int y) {
    if (p[x] < p[y])
        return 1;
    return -1;
}

Subtask #1
0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8420 KB Output is correct
2 Correct 5 ms 8396 KB Output is correct
3 Correct 5 ms 8396 KB Output is correct
4 Correct 5 ms 8396 KB Output is correct
5 Correct 6 ms 8524 KB Output is correct
6 Correct 9 ms 8568 KB Output is correct
7 Correct 80 ms 11320 KB Output is correct
8 Correct 7 ms 8568 KB Output is correct
9 Correct 10 ms 8504 KB Output is correct
10 Correct 97 ms 11380 KB Output is correct
11 Correct 76 ms 11304 KB Output is correct
12 Correct 78 ms 11500 KB Output is correct
13 Correct 77 ms 11332 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8420 KB Output is correct
2 Correct 5 ms 8396 KB Output is correct
3 Correct 5 ms 8396 KB Output is correct
4 Correct 5 ms 8396 KB Output is correct
5 Correct 6 ms 8524 KB Output is correct
6 Correct 9 ms 8568 KB Output is correct
7 Correct 80 ms 11320 KB Output is correct
8 Correct 7 ms 8568 KB Output is correct
9 Correct 10 ms 8504 KB Output is correct
10 Correct 97 ms 11380 KB Output is correct
11 Correct 76 ms 11304 KB Output is correct
12 Correct 78 ms 11500 KB Output is correct
13 Correct 77 ms 11332 KB Output is correct
14 Correct 159 ms 11556 KB Output is correct
15 Correct 957 ms 13984 KB Output is correct
16 Correct 132 ms 11568 KB Output is correct
17 Correct 1056 ms 13980 KB Output is correct
18 Correct 616 ms 13956 KB Output is correct
19 Correct 552 ms 13924 KB Output is correct
20 Correct 850 ms 14016 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8396 KB Output is correct
2 Correct 5 ms 8460 KB Output is correct
3 Correct 68 ms 11240 KB Output is correct
4 Correct 399 ms 16812 KB Output is correct
5 Correct 469 ms 17068 KB Output is correct
6 Correct 704 ms 17256 KB Output is correct
7 Correct 828 ms 17496 KB Output is correct
8 Correct 958 ms 17648 KB Output is correct
9 Correct 483 ms 16992 KB Output is correct
10 Correct 415 ms 17092 KB Output is correct
11 Correct 355 ms 16872 KB Output is correct
12 Correct 451 ms 17008 KB Output is correct
13 Correct 523 ms 17008 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8396 KB Output is correct
2 Correct 6 ms 8396 KB Output is correct
3 Incorrect 5 ms 8396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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