oj.uz

Submission #418934

# Submission time Handle Problem Language Result Execution time Memory
418934 2021-06-06T08:53:08 Z usachevd0 Comparing Plants (IOI20_plants) C++17
44 / 100
 1449 ms 18544 KB 
#include <bits/stdc++.h>
#ifndef LOCAL
    #include "plants.h"
#endif

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

namespace sol {
    const int INF32 = 1e9;
    const int maxN = 2e5 + 5;
    int n, k;
    int r[maxN];
    
    int f[maxN];
    int prior[maxN];

    int md(int i) {
        return (i % n + n) % n;
    }

    bool in_seg(int x, int l, int r) {
        if (l <= r)
            return l <= x && x <= r;
        return x >= l || x <= r;
    }
    
    namespace sgt {
        const int logN = 18;
        const int N = 1 << logN;
        int mn[2][2 * N];
        int lazy[2][2 * N];
        
        void apply(int v, int delta0, int delta1) {
            mn[0][v] += delta0;
            lazy[0][v] += delta0;
            mn[1][v] += delta1;
            lazy[1][v] += delta1;
        }
        void push(int v) {
            // if (!lazy[0][v] && !lazy[1][v]) return;
            apply(v << 1, lazy[0][v], lazy[1][v]);
            apply(v << 1 | 1, lazy[0][v], lazy[1][v]);
            lazy[0][v] = lazy[1][v] = 0;
        }
        void upd(int v) {
            for (int t = 0; t < 2; ++t)
                mn[t][v] = min(mn[t][v << 1], mn[t][v << 1 | 1]);
        }
        
        void build(int v, int vl, int vr) {
            if (vl == vr) {
                mn[0][v] = mn[1][v] = r[vl];
                return;
            }
            int vm = (vl + vr) >> 1;
            build(v << 1, vl, vm);
            build(v << 1 | 1, vm + 1, vr);
            upd(v);
        }
        
        void add(int v, int vl, int vr, int l, int r, int delta0, int delta1) {
            if (l > r || vr < l || r < vl) return;
            if (l <= vl && vr <= r) {
                apply(v, delta0, delta1);
                return;
            }
            int vm = (vl + vr) >> 1;
            push(v);
            add(v << 1, vl, vm, l, r, delta0, delta1);
            add(v << 1 | 1, vm + 1, vr, l, r, delta0, delta1);
            upd(v);
        }
        
        void disable(int v, int vl, int vr, int i, int t) {
            if (vl == vr) {
                mn[t][v] = +INF32;
                return;
            }
            int vm = (vl + vr) >> 1;
            push(v);
            if (i <= vm)
                disable(v << 1, vl, vm, i, t);
            else
                disable(v << 1 | 1, vm + 1, vr, i, t);
            upd(v);
        }
        
        int getFirstZero(int v, int vl, int vr, int t) {
            // debug(v, vl, vr, t, mn[t][v]);
            if (mn[t][v] > 0) return -1;
            if (vl == vr) return vl;
            int vm = (vl + vr) >> 1;
            push(v);
            if (mn[t][v << 1] == 0)
                return getFirstZero(v << 1, vl, vm, t);
            return getFirstZero(v << 1 | 1, vm + 1, vr, t);
        }
        
        int gt(int v, int vl, int vr, int i, int t) {
            if (vl == vr) return mn[t][v];
            int vm = (vl + vr) >> 1;
            push(v);
            if (i <= vm)
                return gt(v << 1, vl, vm, i, t);
            return gt(v << 1 | 1, vm + 1, vr, i, t);
        }
        int gt(int i, int t) {
            return gt(1, 0, n - 1, i, t);
        }
        
        void add(int l, int r, int delta0, int delta1) {
            // cerr << "add " << l << ' ' << r << ' ' << delta0 << ' ' << delta1 << endl;
            if (l <= r)
                add(1, 0, n - 1, l, r, delta0, delta1);
            else {
                add(1, 0, n - 1, 0, r, delta0, delta1);
                add(1, 0, n - 1, l, n - 1, delta0, delta1);
            }
        }
    }
}

void init(int _k, vector<int> _r) {
    using namespace sol;
    n = _r.size();
    k = _k;
    for (int i = 0; i < n; ++i) 
        r[i] = _r[i];
    
    for (int i = 0; i < n; ++i)
        f[i] = r[i];
    // for (int i = 0; i < n; ++i)
    //     if (r[i] == 0)
    //         for (int j = 1; j < k; ++j)
    //             ++f[md(i + j)];
    
    auto dbg = [&]() {
        for (int t = 0; t < 2; ++t) {
            cerr << t << ":   ";
            for (int i = 0; i < n; ++i)
                cerr << sgt::gt(i, t) << ' ';
            cerr << endl;
        }
    };
    
    sgt::build(1, 0, n - 1);
    // dbg();
    for (int i = 0; i < n; ++i)
        if (r[i] == 0) {
            sgt::add(md(i + 1), md(i + k - 1), 0, +1);
            sgt::disable(1, 0, n - 1, i, 0);
        }
    // dbg();
    
    for (int y = 0; y < n; ++y) {
        // mdebug(f, n);
        // assert(count(f, f + n, 0) == 1);
        // int i = find(f, f + n, 0) - f;
        // cerr << "---------------------------------------" << endl;
        // dbg();
        int i = sgt::getFirstZero(1, 0, n - 1, 1);
        // debug(i);
        prior[i] = y;
        // f[i] = +INF32;
        sgt::disable(1, 0, n - 1, i, 0);
        sgt::disable(1, 0, n - 1, i, 1);
        // for (int j = 1; j < k; ++j) {
        //     --f[md(i + j)];
        // }
        sgt::add(md(i + 1), md(i + k - 1), 0, -1);
        // for (int j = 1; j < k; ++j) {
        //     int t = md(i - j);
        //     --f[t];
        //     if (--r[t] == 0) {
        //         for (int j = 1; j < k; ++j)
        //             ++f[md(t + j)];
        //     }
        // }
        sgt::add(md(i - k + 1), md(i - 1), -1, -1);
        for (int j = sgt::getFirstZero(1, 0, n - 1, 0); j != -1; j = sgt::getFirstZero(1, 0, n - 1, 0)) {
            // debug(j);
            sgt::add(md(j + 1), md(j + k - 1), 0, +1);
            sgt::disable(1, 0, n - 1, j, 0);
        }
    }
}

int compare_plants(int x, int y) {
    using namespace sol;
    
    if (prior[x] < prior[y])
        return 1;
    return -1;
}


#ifdef LOCAL

static int n, k, q;
static std::vector<int> r;
static std:: vector<int> x;
static std:: vector<int> y;
static std:: vector<int> answer;
int main() {
    freopen("in", "r", stdin);
    assert(scanf("%d%d%d", &n, &k, &q) == 3);
    r.resize(n);
    answer.resize(q);
    for (int i = 0; i < n; i++) {
        int value;
        assert(scanf("%d", &value) == 1);
        r[i] = value;
    }
    x.resize(q);
    y.resize(q);
    for (int i = 0; i < q; i++) {
        assert(scanf("%d%d", &x[i], &y[i]) == 2);
    }
    fclose(stdin);

    init(k, r);
    for (int i = 0; i < q; i++) {
        answer[i] = compare_plants(x[i], y[i]);
    }

    for (int i = 0; i < q; i++) {
        printf("%d\n", answer[i]);
    }

    fclose(stdout);

    return 0;
}


// int32_t main() {
//     #ifdef LOCAL
//         freopen("in", "r", stdin);
//     #endif
//     ios::sync_with_stdio(0);
//     cin.tie(0);
    
    
    
    
//     return 0;
// }
#endif

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:184:10: warning: variable 'dbg' set but not used [-Wunused-but-set-variable]
  184 |     auto dbg = [&]() {
      |          ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Incorrect 0 ms 332 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 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 5 ms 460 KB Output is correct
7 Correct 77 ms 3444 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 7 ms 332 KB Output is correct
10 Correct 76 ms 3444 KB Output is correct
11 Correct 74 ms 3396 KB Output is correct
12 Correct 75 ms 3600 KB Output is correct
13 Correct 93 ms 3444 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 5 ms 460 KB Output is correct
7 Correct 77 ms 3444 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 7 ms 332 KB Output is correct
10 Correct 76 ms 3444 KB Output is correct
11 Correct 74 ms 3396 KB Output is correct
12 Correct 75 ms 3600 KB Output is correct
13 Correct 93 ms 3444 KB Output is correct
14 Correct 166 ms 4488 KB Output is correct
15 Correct 1362 ms 18476 KB Output is correct
16 Correct 152 ms 6716 KB Output is correct
17 Correct 1449 ms 18472 KB Output is correct
18 Correct 1163 ms 18024 KB Output is correct
19 Correct 1140 ms 18532 KB Output is correct
20 Correct 1310 ms 18544 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 61 ms 3180 KB Output is correct
4 Correct 842 ms 17744 KB Output is correct
5 Correct 952 ms 17956 KB Output is correct
6 Correct 1110 ms 18048 KB Output is correct
7 Correct 1251 ms 18252 KB Output is correct
8 Correct 1305 ms 18444 KB Output is correct
9 Correct 855 ms 17784 KB Output is correct
10 Correct 872 ms 17796 KB Output is correct
11 Correct 723 ms 17568 KB Output is correct
12 Correct 893 ms 17972 KB Output is correct
13 Correct 1114 ms 18028 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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