oj.uz

Submission #434723

# Submission time Handle Problem Language Result Execution time Memory
434723 2021-06-21T15:40:25 Z yuto1115 Comparing Plants (IOI20_plants) C++17
11 / 100
 166 ms 5476 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; i--)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

// min, arg_min
using S = pair<int, int>;

const S e = {inf, -1};

S op(const S &l, const S &r) {
    return (l.first <= r.first ? l : r);
}

using F = int;

const F id = 0;

F composition(const F &g, const F &f) {
    return g + f;
}

S mapping(const F &f, const S &x) {
    return S(x.first + f, x.second);
}

class lazy_segtree {
    int log, n;
    vector<S> d;
    vector<F> lazy;
    
    void update(int i) {
        assert(i < n);
        d[i] = op(d[2 * i], d[2 * i + 1]);
    }
    
    void all_apply(int i, const F &f) {
        d[i] = mapping(f, d[i]);
        if (i < n) lazy[i] = composition(f, lazy[i]);
    }
    
    void propagate(int i) {
        assert(i < n);
        all_apply(2 * i, lazy[i]);
        all_apply(2 * i + 1, lazy[i]);
        lazy[i] = id;
    }

public:
    lazy_segtree(const vector<S> &init) {
        log = 0;
        while ((1 << log) < init.size()) log++;
        n = 1 << log;
        d.assign(2 * n, e);
        rep(i, init.size()) d[n + i] = init[i];
        rrep(i, n) update(i);
        lazy.assign(n, id);
    }
    
    S prod(int l, int r) {
        assert(0 <= l and l <= r and r <= n);
        l += n, r += n;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) propagate(l >> i);
            if (((r >> i) << i) != r) propagate(r >> i);
        }
        S fl = e, fr = e;
        while (l < r) {
            if (l & 1) fl = op(fl, d[l++]);
            if (r & 1) fr = op(d[--r], fr);
            l >>= 1, r >>= 1;
        }
        return op(fl, fr);
    }
    
    void apply(int l, int r, const F &f) {
        assert(0 <= l and l <= r and r <= n);
        l += n, r += n;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) propagate(l >> i);
            if (((r >> i) << i) != r) propagate(r >> i);
        }
        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1, r >>= 1;
            }
            l = l2, r = r2;
        }
        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update(r >> i);
        }
    }
};

int k, n;
vi p;
vvi v;
vi to, rev;

void init(int _k, vi r) {
    k = _k;
    n = r.size();
    vector<S> init(n);
    rep(i, n) init[i] = {r[i], i};
    lazy_segtree st(init);
    set<int> can;
    auto get_min = [&](int i, int w) {
        if (i >= w) return st.prod(i - w, i);
        int rem = w - i;
        return op(st.prod(n - rem, n), st.prod(0, i));
    };
    auto dec = [&](int i) {
        if (i >= k - 1) {
            st.apply(i - k + 1, i, -1);
            return;
        }
        int rem = k - 1 - i;
        st.apply(n - rem, n, -1);
        st.apply(0, i, -1);
    };
    auto check = [&](int i) {
        S s = get_min(i, k - 1);
        if (s.first > 0) can.insert(i);
    };
    auto erase = [&](int i) {
        st.apply(i, i + 1, inf);
        dec(i);
        S s = get_min(i, k - 1);
        if (s.first == 0) check(s.second);
        s = get_min(i, n - 1);
        if (s.first == 0) check(s.second);
    };
    if (n <= 300) {
        v.resize(n);
        rep(i, n) {
            v[i].resize(n);
            st = lazy_segtree(init);
            can.clear();
            rep(j, n) if (!r[j]) check(j);
            while (true) {
                if (can.count(i)) can.erase(i);
                if (can.empty()) break;
                int nx = *can.begin();
                can.erase(nx);
                v[i][nx] = 1;
                erase(nx);
            }
        }
    } else {
        p.assign(n, -1);
        rep(i, n) if (!r[i]) check(i);
        rrep(t, n) {
            int nx = *can.begin();
            can.erase(nx);
            p[nx] = t;
            erase(nx);
        }
        to.resize(n);
        {
            st = lazy_segtree(init);
            can.clear();
            rep(j, n) if (!r[j]) check(j);
            while (true) {
                if (can.count(0)) can.erase(0);
                if (can.empty()) break;
                int nx = *can.begin();
                can.erase(nx);
                to[nx] = 1;
                erase(nx);
            }
        }
        rev.resize(n);
        rep(i, n) init[i] = {k - 1 - r[i], i};
        {
            st = lazy_segtree(init);
            can.clear();
            rep(j, n) if (!r[j]) check(j);
            while (true) {
                if (can.count(0)) can.erase(0);
                if (can.empty()) break;
                int nx = *can.begin();
                can.erase(nx);
                rev[nx] = 1;
                erase(nx);
            }
        }
    }
}

int compare_plants(int x, int y) {
    if (n <= 300) {
        assert(v[x][y] or v[y][x]);
        if (v[x][y] and v[y][x]) return 0;
        return (v[x][y] ? -1 : 1);
    } else if (x == 0) {
        assert(to[y] or rev[y]);
        if (to[y] and rev[y]) return 0;
        return (to[y] ? -1 : 1);
    } else {
        return (p[x] > p[y] ? 1 : -1);
    }
}

Compilation message

plants.cpp: In constructor 'lazy_segtree::lazy_segtree(const std::vector<std::pair<int, int> >&)':
plants.cpp:89:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         while ((1 << log) < init.size()) log++;
      |                ~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 5.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 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 57 ms 3020 KB Output is correct
7 Incorrect 166 ms 4488 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 6 ms 332 KB Output is correct
6 Runtime error 4 ms 588 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 6 ms 332 KB Output is correct
6 Runtime error 4 ms 588 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 9 ms 332 KB Output is correct
7 Correct 101 ms 1264 KB Output is correct
8 Correct 73 ms 1244 KB Output is correct
9 Correct 76 ms 1272 KB Output is correct
10 Correct 73 ms 1220 KB Output is correct
11 Correct 94 ms 1264 KB Output is correct
12 Correct 78 ms 1248 KB Output is correct
13 Correct 106 ms 1220 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Runtime error 4 ms 588 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.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 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 57 ms 3020 KB Output is correct
7 Incorrect 166 ms 4488 KB Output isn't correct
8 Halted 0 ms 0 KB -