oj.uz

Submission #75060

# Submission time Handle Problem Language Result Execution time Memory
75060 2018-09-08T08:07:22 Z dacin21 Meetings (IOI18_meetings) C++14
100 / 100
 4239 ms 353996 KB 
// 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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 560 KB Output is correct
3 Correct 8 ms 568 KB Output is correct
4 Correct 8 ms 564 KB Output is correct
5 Correct 8 ms 504 KB Output is correct
6 Correct 7 ms 524 KB Output is correct
7 Correct 8 ms 496 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 7 ms 632 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 560 KB Output is correct
3 Correct 8 ms 568 KB Output is correct
4 Correct 8 ms 564 KB Output is correct
5 Correct 8 ms 504 KB Output is correct
6 Correct 7 ms 524 KB Output is correct
7 Correct 8 ms 496 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 7 ms 632 KB Output is correct
10 Correct 16 ms 1060 KB Output is correct
11 Correct 15 ms 996 KB Output is correct
12 Correct 17 ms 1056 KB Output is correct
13 Correct 15 ms 988 KB Output is correct
14 Correct 15 ms 1132 KB Output is correct
15 Correct 16 ms 1136 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 59 ms 4716 KB Output is correct
3 Correct 346 ms 15780 KB Output is correct
4 Correct 301 ms 14068 KB Output is correct
5 Correct 331 ms 17316 KB Output is correct
6 Correct 314 ms 17388 KB Output is correct
7 Correct 304 ms 15752 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 59 ms 4716 KB Output is correct
3 Correct 346 ms 15780 KB Output is correct
4 Correct 301 ms 14068 KB Output is correct
5 Correct 331 ms 17316 KB Output is correct
6 Correct 314 ms 17388 KB Output is correct
7 Correct 304 ms 15752 KB Output is correct
8 Correct 345 ms 14268 KB Output is correct
9 Correct 261 ms 14120 KB Output is correct
10 Correct 349 ms 15620 KB Output is correct
11 Correct 338 ms 14180 KB Output is correct
12 Correct 264 ms 14072 KB Output is correct
13 Correct 349 ms 15524 KB Output is correct
14 Correct 333 ms 15692 KB Output is correct
15 Correct 316 ms 14064 KB Output is correct
16 Correct 315 ms 16300 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 560 KB Output is correct
3 Correct 8 ms 568 KB Output is correct
4 Correct 8 ms 564 KB Output is correct
5 Correct 8 ms 504 KB Output is correct
6 Correct 7 ms 524 KB Output is correct
7 Correct 8 ms 496 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 7 ms 632 KB Output is correct
10 Correct 16 ms 1060 KB Output is correct
11 Correct 15 ms 996 KB Output is correct
12 Correct 17 ms 1056 KB Output is correct
13 Correct 15 ms 988 KB Output is correct
14 Correct 15 ms 1132 KB Output is correct
15 Correct 16 ms 1136 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 59 ms 4716 KB Output is correct
18 Correct 346 ms 15780 KB Output is correct
19 Correct 301 ms 14068 KB Output is correct
20 Correct 331 ms 17316 KB Output is correct
21 Correct 314 ms 17388 KB Output is correct
22 Correct 304 ms 15752 KB Output is correct
23 Correct 345 ms 14268 KB Output is correct
24 Correct 261 ms 14120 KB Output is correct
25 Correct 349 ms 15620 KB Output is correct
26 Correct 338 ms 14180 KB Output is correct
27 Correct 264 ms 14072 KB Output is correct
28 Correct 349 ms 15524 KB Output is correct
29 Correct 333 ms 15692 KB Output is correct
30 Correct 316 ms 14064 KB Output is correct
31 Correct 315 ms 16300 KB Output is correct
32 Correct 2979 ms 97916 KB Output is correct
33 Correct 2045 ms 97884 KB Output is correct
34 Correct 3211 ms 97972 KB Output is correct
35 Correct 3013 ms 97980 KB Output is correct
36 Correct 2075 ms 97916 KB Output is correct
37 Correct 3229 ms 98008 KB Output is correct
38 Correct 3165 ms 102276 KB Output is correct
39 Correct 4239 ms 353996 KB Output is correct
40 Correct 3261 ms 97696 KB Output is correct
41 Correct 3349 ms 97492 KB Output is correct
42 Correct 3472 ms 97340 KB Output is correct
43 Correct 3480 ms 97244 KB Output is correct
44 Correct 3513 ms 97236 KB Output is correct