oj.uz

Submission #418994

# Submission time Handle Problem Language Result Execution time Memory
418994 2021-06-06T09:56:24 Z usachevd0 Comparing Plants (IOI20_plants) C++17
27 / 100
 1336 ms 32804 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 par[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;
    }
    
    vector<int> tree[maxN];
    int tin[maxN], tout[maxN], timer;
    void dfs(int v) {
        tin[v] = timer++;
        for (int u : tree[v])
            dfs(u);
        tout[v] = timer - 1;
    }
    bool parent(int a, int b) {
        return tin[a] <= tin[b] && tout[b] <= tout[a];
    }
    
    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) {
            lazy[0][v] = lazy[1][v] = 0;
            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 dbg() {
    using namespace sol;
    for (int t = 0; t < 2; ++t) {
        cerr << t << ":   ";
        for (int i = 0; i < n; ++i)
            cerr << sgt::gt(i, t) << ' ';
        cerr << endl;
    }
}

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];
    
    
    
    
    sgt::build(1, 0, n - 1);
    // dbg();
    set<int> zeroes;
    memset(par, 255, sizeof par);
    auto processf0 = [&](int p) {
        for (int i = sgt::getFirstZero(1, 0, n - 1, 1); i != -1; i = sgt::getFirstZero(1, 0, n - 1, 1)) {
            zeroes.insert(i);
            par[i] = p;
            sgt::disable(1, 0, n - 1, i, 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);
        }
    
    processf0(-1);

    for (int y = 0; y < n; ++y) {
        int i = *zeroes.begin();
        zeroes.erase(zeroes.begin());
        // debug(i);
        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);
        }
        processf0(i);
    }
    
    for (int i = 0; i < n; ++i) {
        // debug(i, par[i]);
        if (par[i] != -1)
            tree[par[i]].push_back(i);
    }
    for (int i = 0; i < n; ++i)
        if (par[i] == -1)
            dfs(i);
}

int compare_plants(int x, int y) {
    using namespace sol;
    
    if (parent(x, y))
        return 1;
    if (parent(y, x))
        return -1;
    return 0;
}


#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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5708 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Incorrect 3 ms 5708 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 3 ms 5708 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 4 ms 5836 KB Output is correct
6 Correct 8 ms 5960 KB Output is correct
7 Correct 84 ms 9412 KB Output is correct
8 Correct 5 ms 5836 KB Output is correct
9 Correct 8 ms 5964 KB Output is correct
10 Correct 81 ms 9284 KB Output is correct
11 Correct 78 ms 9172 KB Output is correct
12 Correct 78 ms 9428 KB Output is correct
13 Correct 84 ms 9296 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5708 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 4 ms 5836 KB Output is correct
6 Correct 8 ms 5960 KB Output is correct
7 Correct 84 ms 9412 KB Output is correct
8 Correct 5 ms 5836 KB Output is correct
9 Correct 8 ms 5964 KB Output is correct
10 Correct 81 ms 9284 KB Output is correct
11 Correct 78 ms 9172 KB Output is correct
12 Correct 78 ms 9428 KB Output is correct
13 Correct 84 ms 9296 KB Output is correct
14 Correct 152 ms 11216 KB Output is correct
15 Correct 1336 ms 32652 KB Output is correct
16 Correct 155 ms 11332 KB Output is correct
17 Correct 1303 ms 32804 KB Output is correct
18 Correct 1060 ms 32776 KB Output is correct
19 Correct 1085 ms 32708 KB Output is correct
20 Correct 1244 ms 32752 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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