Submission #75060

#	Time	Username	Problem	Language	Result	Execution time	Memory
75060		dacin21	Meetings (IOI18_meetings)	C++14	100 / 100	4239 ms	353996 KiB

meetings

// 100 p
#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>

#ifdef LOCAL_RUN
#include "prettyprint.hpp"
#endif // LOCAL_RUN


#define debug(x) do{}while(0)

using namespace std;

using ll = long long;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
constexpr int inf = 1e9;

// could maybe be optimized by transposing
template<typename T = int, typename comp = greater<T>>
class Sparsetable{
    int compind(int i, int j, int l, int sign)const{
        i = RMQ[lgn*i+l], j=RMQ[lgn*(j+sign*(1<<l))+l];
        return comp()(data[i], data[j])? i : j;
    }
    int minind(int l, int r)const{
		assert(l<r);
        return compind(l, r, lg2[r-l],-1);
    }
    void build(){
        lg2.resize(n+1);
        for(int i=2;i<=n;++i) lg2[i]=1+lg2[i/2];
        lgn = lg2.back()+1;
        RMQ.resize(n*lgn);
        for(int i=n-1;i>=0;--i){
            RMQ[lgn*i]=i;
            for(int j=0;j<lg2[n-i];++j) RMQ[lgn*i+j+1] = compind(i,i,j,1);
        }
    }
    public:
    Sparsetable(T const*v, int _N):n(_N), data(v, v+_N){build();}
    Sparsetable(vector<T> const&v):Sparsetable(v.data(), v.size()){};
    // min in [l, r)
    pair<int, T&> operator()(int const&i, int const&j){
        int k = minind(i, j);
        return pair<int, T&>(k, data[k]);
    }
    int n, lgn;
    vector<int> RMQ, lg2;
    vector<T> data;
};


struct Node{
    int l_size, r_size;
    pair<int, int> val;
    ll l_dp, r_dp, dp;
    int get_size(){return l_size + r_size + 1;}
    void recalc_dp(){
        ll cand1 = l_dp + (r_size+1)*(ll)val.first;
        ll cand2 = r_dp + (l_size+1)*(ll)val.first;
        dp = min(cand1, cand2);
    }
};

int n, q;

vector<pair<int, int> > calc_maxval(vector<pair<int, int>> const&H, vector<int> const&L, vector<int> const&R){
    Sparsetable<pair<int, int> > s(H);
    vector<pair<int, int>> ret(q);
    for(int i=0;i<q;++i){
        ret[i] = s(L[i], R[i]+1).second;
    }
    return ret;
}

struct Block{
    struct Node{
        pair<int, int> val;
        ll dp_base;
        int l_size;
        ll l_add() const {
            return (l_size+1)*(ll)val.first;
        }
        bool operator<(pair<int, int> const&o) const {
            return val < o;
        }
        bool operator>(pair<int, int> const&o) const {
            return val > o;
        }

        friend ostream& operator<<(ostream&o, Node const&n){
#ifdef LOCAL_RUN
            return o << n.val << " " << n.dp_base << " " << n.l_size;
#else
            return o;
#endif
        }
    };
    deque<Node> nodes;
    ll a, b;// globally add a*x+b
    // returns (r_dp of max, index of max)
    Block(){}
    Block(Node const&n, ll a_, ll b_):nodes(1, n), a(a_), b(b_){}
    pair<ll, int> query(pair<int, int> const&val, int t){
        debug(cerr << "Query " << (*this)  << "  " << val << " " << t << "\n");
        auto it = lower_bound(nodes.begin(), nodes.end(), val, std::greater<>());
        assert(it != nodes.end() && it->val == val);
        const int index = it->val.second;
        ++it;
        // dp_r is in next block
        if(it == nodes.end()){
            return make_pair(-1, index);
        }
        return make_pair(it->dp_base + a*t + b, index);
    }
    ll query_dp_r(int t){
        const Node& n = nodes.front();
        return n.dp_base + a*t + b;
    }
    // TODO: fix
    static Block merge(Block &&l, Block &&r){
        // make l's dp depend on r
        const Node& n1 = l.nodes.back(), n2 = r.nodes.front();
        ll l_new_add = -n1.dp_base + n2.dp_base + n1.l_add() - l.b + r.b;
        l.b += l_new_add;
        l.a = r.a;
        // update dp at back
        Block *a = &l, *b = &r;
        if(a->nodes.size() > b->nodes.size()){
            swap(a, b);
        }
        for(auto &e:a->nodes){
            e.dp_base += (a->b - b->b);
        }
        a->b = b->b;
        if(l.nodes.size() < r.nodes.size()){
            r.nodes.insert(r.nodes.begin(), l.nodes.begin(), l.nodes.end());
            return move(r);
        } else {
            l.nodes.insert(l.nodes.end(), r.nodes.begin(), r.nodes.end());
            return move(l);
        }
    }
    // returns (index, dp)
    pair<int, ll> intersect(pair<int, int> const&val, int dir){
        pair<int, ll> ret(-1, -1);
        while(!nodes.empty() && nodes.back().val <= val){
            const int index = nodes.back().val.second;
            ret = make_pair(index-dir*nodes.back().l_size, nodes.back().dp_base + a*(val.second-dir) + b);
            nodes.pop_back();
        }
        return ret;
    }
    int calc_intersection(Block const&r, bool const& rev){
        const ll m1 = a, q1 = nodes.back().dp_base + b;
        const ll m2 = r.a, q2 = r.nodes.front().dp_base + r.b + nodes.back().l_add();
        debug(cerr << "intersect " << m1 << " " << q1 << " | " << m2 << " " << q2 << "\n");
        if(m1 == m2){
            if(q2 <= q1){ // already intersected
                return rev ? inf : -inf;
            } else { // won't ever intersect
                return rev ? -inf : inf;
            }
        } else {
            // intersection at (q2-q1)/(m1-m2) -> round correctly
            long double tmp = (q2 - q1) / (long double)(m1 - m2);
            if(tmp < -inf) return -inf;
            if(tmp > inf) return inf;
            return rev ? floor(tmp) : ceil(tmp);
        }
    }
    friend ostream& operator<<(ostream&o, Block const&b){

#ifdef LOCAL_RUN
        return o << "Block: " << b.a << "*x + " << b.b << " : " << b.nodes;
#else
        return o;
#endif
    }
};

vector<pair<int, ll> > sweep(vector<pair<int, int>> const&H, vector<pair<int, int>> const&M, vector<int> const&R, bool const rev){
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    const int dir = rev ? -1 : 1;
    if(rev){
        reverse(ord.begin(), ord.end());
    }
    vector<vector<int> > ev(n);
    for(int i=0;i<q;++i){
        ev[R[i]].push_back(i);
    }
    map<pair<int, int>, Block> s;
    vector<pair<int, ll> > ret(q);
    min_heap<array<int, 3> > inters;
    auto add_event = [&](map<pair<int, int>, Block>::iterator it){
        assert(it != s.end());
        auto it2 = next(it);
        if(it2 == s.end()) return;
        int inter = it2->second.calc_intersection(it->second, rev);
        inters.push({inter*dir, it->first.first, it->first.second});
    };
    for(auto const&e:ord){
        // add element to cartesian tree
        Block::Node n{H[e], 0, 0};
        auto it = s.begin();
        for(;it != s.end();++it){
            auto tmp = it->second.intersect(H[e], dir);
            if(tmp.first == -1 && tmp.second == -1){
                break;
            }
            n.l_size = abs(e - tmp.first);
            n.dp_base = tmp.second;
        }
        if(it != s.begin()){
            --it;
            s.erase(s.begin(), it);
            if(it->second.nodes.empty()) s.erase(it);
        }
        s[H[e]] = Block(n, n.val.first*dir, -n.val.first*dir * (ll)n.val.second + n.val.first);
        add_event(s.begin());
        // process intersection events

        while(!inters.empty() && inters.top()[0] <= dir*e){
            auto inter = inters.top();
            inters.pop();
            pair<int, int> l = make_pair(inter[1], inter[2]);
            auto it = s.find(l);
            if(it == s.end()) continue;
            auto it2 = next(it);
            if(it2 == s.end()) continue;
            int real_inter = it2->second.calc_intersection(it->second, rev);
            if(inter[0] != real_inter*dir) continue;
            it2->second = Block::merge(move(it2->second), move(it->second));
            s.erase(it);
            add_event(it2);
        }
        debug(cerr << e << " : " << s << "\n");
        // process queries
        for(auto const&f : ev[e]){
            auto it = s.lower_bound(M[f]);
            assert(it != s.end());
            pair<ll, int> ans = it->second.query(M[f], e);
            if(ans.first == -1){
                if(it == s.begin()){
                    ans.first = 0;
                } else {
                    ans.first = prev(it)->second.query_dp_r(e);
                }
            }
            ret[f] = make_pair(abs(e-ans.second), ans.first);
        }
        //cerr << inters << "\n";
    }
    debug(cerr << "sweep\n" << R << "\n" << M << "\n" << ret << "\n");
    return ret;
}

vector<pair<int, ll> > sweep_slow(vector<pair<int, int>> const&H, vector<pair<int, int>> const&M, vector<int> const&R, bool const rev){
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    if(rev){
        reverse(ord.begin(), ord.end());
    }
    vector<vector<int> > ev(n);
    for(int i=0;i<q;++i){
        ev[R[i]].push_back(i);
    }
    vector<Node> s;
    vector<pair<int, ll> > ret(q);
    for(auto const&e:ord){
        // add element to cartesian tree
        Node n{0, 0, H[e], 0, 0, H[e].first};
        while(!s.empty() && n.val >= s.back().val){
            n.l_size = s.back().get_size();
            n.l_dp = s.back().dp;
            s.pop_back();
        }
        n.recalc_dp();
        s.push_back(n);
        for(auto it = s.rbegin(), it2=next(it);it2!=s.rend();it = it2, it2 = next(it)){
            ++(it2->r_size);
            it2->r_dp = it->dp;
            it2->recalc_dp();
        }
        // process queries
        for(auto const&f : ev[e]){
            int i=0;
            while(s[i].val > M[f]) ++i;
            assert(s[i].val == M[f]);
            ret[f] = make_pair(s[i].r_size, s[i].r_dp);
        }
    }
    //cerr << "sweep\n" << R << "\n" << M << "\n" << ret << "\n";
    return ret;
}

vector<ll> minimum_costs(vector<int> HH, vector<int> L, vector<int> R){
    assert(L.size() == R.size());
    n = HH.size();
    q = R.size();
    vector<pair<int, int> > H(n);
    for(int i=0;i<n;++i){
        H[i] = make_pair(HH[i], i);
    }
    const vector<pair<int, int> > M = calc_maxval(H, L, R);
    vector<pair<int, ll> > cost_R = sweep(H, M, R, false);
    vector<pair<int, ll> > cost_L = sweep(H, M, L, true);
    vector<ll> ret(q);
    for(int i=0;i<q;++i){
        ll cand1 = M[i].first*(ll)(R[i]-L[i]+1-cost_L[i].first) + cost_L[i].second;
        ll cand2 = M[i].first*(ll)(R[i]-L[i]+1-cost_R[i].first) + cost_R[i].second;
        debug(cerr << cand1 << " / " << cand2 << "\n");
        ret[i] = min(cand1, cand2);
    }
    return ret;
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 40 / 40