oj.uz

Submission #433608

# Submission time Handle Problem Language Result Execution time Memory
433608 2021-06-20T08:24:27 Z usachevd0 Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 5208 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;
}

namespace sgt {
    const int N = 1 << logN;
    int mn[2 * N];
    int 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]);
    }

    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) {
        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);
    }
}

void init(int _k, vector<int> _r) {
    n = _r.size(), k = _k;
    for (int i = 0; i < n; ++i)
        r[i] = _r[i];
    vector<int> f(all(_r));
    for (int i = 0; i < n; ++i)
        if (!r[i]) {
            for (int t = 1; t < k; ++t)
                ++f[md(i + t)];
            r[i] = +INF32;
        }
    // sgt::build(r);
    // for (int i = 0; i < n; ++i)
    //     if (!r[i])
    //         sgt::add(md(i + 1), md(i + k - 1), +1);
    for (int v = 0; v < n; ++v) {
        // int i = sgt::GetFirstZero(1, 0, sgt::N - 1, 0, n - 1);
        // sgt::disable(1, 0, sgt::N - 1, i);
        // sgt::add(md(i + 1), md(i + k - 1), -1);
        // sgt::add(md(i - k + 1), md(i - 1), -1);
        assert(count(all(f), 0) == 1);
        int i = find(all(f), 0) - f.begin();
        f[i] = +INF32;
        for (int t = 1; t < k; ++t) {
            --f[md(i + t)];
            --f[md(i - t)];
            --r[md(i - t)];
        }
        for (int i = 0; i < n; ++i)
            if (!r[i]) {
                for (int t = 1; t < k; ++t)
                    ++f[md(i + t)];
                r[i] = +INF32;
            }
        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 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Runtime error 2 ms 460 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 18 ms 332 KB Output is correct
7 Correct 440 ms 5084 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 17 ms 432 KB Output is correct
10 Correct 429 ms 5096 KB Output is correct
11 Correct 308 ms 5080 KB Output is correct
12 Correct 303 ms 5208 KB Output is correct
13 Correct 507 ms 5036 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 18 ms 332 KB Output is correct
7 Correct 440 ms 5084 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 17 ms 432 KB Output is correct
10 Correct 429 ms 5096 KB Output is correct
11 Correct 308 ms 5080 KB Output is correct
12 Correct 303 ms 5208 KB Output is correct
13 Correct 507 ms 5036 KB Output is correct
14 Execution timed out 4061 ms 5148 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Runtime error 1 ms 396 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Runtime error 1 ms 460 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Runtime error 2 ms 460 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -