oj.uz

Submission #418957

# Submission time Handle Problem Language Result Execution time Memory
418957 2021-06-06T09:15:26 Z usachevd0 Comparing Plants (IOI20_plants) C++17
44 / 100
 1329 ms 14148 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 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];
    
    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);
    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);
        }
    for (int y = 0; y < n; ++y) {
        int i = sgt::getFirstZero(1, 0, n - 1, 1);
        prior[i] = y;
        sgt::disable(1, 0, n - 1, i, 0);
        sgt::disable(1, 0, n - 1, i, 1);
        sgt::add(md(i + 1), md(i + k - 1), 0, -1);
        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)) {
            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:176:10: warning: variable 'dbg' set but not used [-Wunused-but-set-variable]
  176 |     auto dbg = [&]() {
      |          ^~~

Subtask #1
0 / 5.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 Incorrect 1 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 1 ms 332 KB Output is correct
3 Correct 1 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 3488 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 5 ms 332 KB Output is correct
10 Correct 79 ms 3448 KB Output is correct
11 Correct 77 ms 3408 KB Output is correct
12 Correct 76 ms 3556 KB Output is correct
13 Correct 80 ms 3524 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 1 ms 332 KB Output is correct
3 Correct 1 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 3488 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 5 ms 332 KB Output is correct
10 Correct 79 ms 3448 KB Output is correct
11 Correct 77 ms 3408 KB Output is correct
12 Correct 76 ms 3556 KB Output is correct
13 Correct 80 ms 3524 KB Output is correct
14 Correct 174 ms 4404 KB Output is correct
15 Correct 1329 ms 13984 KB Output is correct
16 Correct 150 ms 4404 KB Output is correct
17 Correct 1313 ms 13980 KB Output is correct
18 Correct 1101 ms 13968 KB Output is correct
19 Correct 1128 ms 14040 KB Output is correct
20 Correct 1194 ms 13984 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 1 ms 332 KB Output is correct
3 Correct 64 ms 3192 KB Output is correct
4 Correct 807 ms 14096 KB Output is correct
5 Correct 906 ms 14148 KB Output is correct
6 Correct 1100 ms 13980 KB Output is correct
7 Correct 1223 ms 13984 KB Output is correct
8 Correct 1291 ms 14024 KB Output is correct
9 Correct 852 ms 14056 KB Output is correct
10 Correct 862 ms 14032 KB Output is correct
11 Correct 728 ms 13924 KB Output is correct
12 Correct 889 ms 13932 KB Output is correct
13 Correct 1082 ms 13992 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Incorrect 0 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 1 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 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -