Submission #434724

#	Time	Username	Problem	Language	Result	Execution time	Memory
434724		yuto1115	Comparing Plants (IOI20_plants)	C++17	70 / 100	1460 ms	19064 KiB

plants

#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] == k - 1) 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 (stderr)

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
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 11 / 11
• Subtask 6: 15 / 15
• Subtask 7: 0 / 25