Submission #597745

#	Time	Username	Problem	Language	Result	Execution time	Memory
597745		Lucpp	Meetings (IOI18_meetings)	C++17	100 / 100	2222 ms	308624 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
using namespace std;
typedef long long ll;
const ll INF = 1e18;

struct Seg{
    int cap;
    vector<pair<ll, int>> seg;
    void init(vector<ll> v){
        for(cap = 1; cap < sz(v); cap *= 2);
        seg.resize(2*cap);
        for(int i = 0; i < cap; i++) seg[i+cap].second = i;
        for(int i = 0; i < sz(v); i++) seg[i+cap].first = v[i];
        for(int i = cap-1; i >= 1; --i) seg[i] = max(seg[2*i], seg[2*i+1]);
    }
    pair<ll, int> qry(int l, int r, int a, int b, int i){
        if(l <= a && b <= r) return seg[i];
        if(b < l || r < a) return {-INF, -1};
        int m = (a+b)/2;
        return max(qry(l, r, a, m, 2*i), qry(l, r, m+1, b, 2*i+1));
    }
    int argmax(int l, int r){return qry(l, r, 1, cap, 1).second;}
};

vector<ll> H;
vector<int> lc, rc;

struct Lin{
    ll a, b; // a + b*x
};
set<pair<int, int>> s;
vector<Lin> lin;
vector<ll> add;

vector<ll> answer;
vector<vector<tuple<int, int, int>>> query;

ll get(int i){
    int j = (--s.lower_bound({i+1, 0}))->first;
    return lin[j].a + lin[j].b*(i-j);
}

void calc(int i, int start, int end){
    if(lc[i] != -1) calc(lc[i], start, i-1);
    if(rc[i] != -1) calc(rc[i], i+1, end);
    for(auto [L, R, ind] : query[i]){
        answer[ind] = H[i]*(i+1-L) + (R>i ? add[rc[i]]+get(R) : 0);
    }
    if(lc[i] == -1 && rc[i] == -1){
        s.emplace(i, i);
        lin[i] = {H[i], 0};
    }
    else if(rc[i] == -1){
        s.emplace(i, i);
        lin[i] = {H[i]+get(i-1), 0};
        add[i] = add[lc[i]];
    }
    else if(lc[i] == -1){
        s.emplace(i, i);
        add[i] = add[rc[i]]+H[i];
        lin[i] = {H[i]-add[i], 0};
    }
    else{
        s.emplace(i, i);
        lin[i] = {H[i]+get(i-1), 0};
        ll le = lin[i].a + add[lc[i]];
        int until = end;
        auto it = s.lower_bound({i+1, 0});
        while(it != s.end() && it->first <= end){
            Lin li = lin[it->first];
            ll y = add[rc[i]] + li.a + li.b*(it->second-it->first);
            // cerr << le + (it->second-i)*H[i] << " " << y + (i+1-start)*H[i] << "\n";
            if(le + (it->second-i)*H[i] <= y + (i+1-start)*H[i]) it = s.erase(it);
            else{
                int j = int(((2*i+1-start)*H[i]+add[rc[i]]+li.a-li.b*it->first-le)/(H[i]-li.b))+1;
                // cerr << j << " " << le << " " << add[rc[i]] << " " << lin[it->first].a << " " << lin[it->first].b << "\n";
                int r = it->second;
                assert(j <= r);
                until = max(j, it->first)-1;
                if(j > it->first){
                    lin[j] = {li.a+li.b*(j-it->first), li.b};
                    s.erase(it);
                    s.emplace(j, r);
                }
                break;
            }
        }
        // cerr << le << "\n";
        add[rc[i]] += (i+1-start)*H[i];
        if(until > i){
            s.emplace(i+1, until);
            lin[i+1] = {le-add[rc[i]]+H[i], H[i]};
        }
        if(i-start < end-i){
            add[i] = add[rc[i]];
            it = s.lower_bound({start, 0});
            for(; it != s.end() && it->first <= i; it++){
                lin[it->first].a += add[lc[i]]-add[i];
            }
        }
        else{
            add[i] = add[lc[i]];
            it = s.lower_bound({i+1, 0});
            for(; it != s.end() && it->first <= end; it++){
                lin[it->first].a += add[rc[i]]-add[i];
            }
        }
    }
    // cerr << "## " << i << " ##\n";
    // auto it = s.lower_bound({start, 0});
    // cerr << lc[i] << " " << rc[i] << " " << add[i] << "\n";
    // for(; it != s.end() && it->first <= end; it++){
    //     cerr << it->first << " " << it->second << "   " << lin[it->first].a << " " << lin[it->first].b << "\n";
    // }
}

vector<ll> solve(int n, int q, int root){
    s.clear();
    answer.assign(q, 0);
    add.assign(n, 0);
    calc(root, 0, n-1);
	return answer;
}

vector<ll> minimum_costs(vector<int> h, vector<int> L, vector<int> R){
    int n = sz(h);
    int q = sz(L);
    H.resize(n);
    for(int i = 0; i < n; i++) H[i] = h[i];
    lc.assign(n, -1);
    rc.assign(n, -1);
    stack<pair<int, int>> st;
    for(int i = 0; i < n; i++){
        while(!st.empty() && st.top().first <= H[i]){
            lc[i] = st.top().second;
            st.pop();
        }
        if(!st.empty()) rc[st.top().second] = i;
        st.emplace(H[i], i);
    }
    Seg seg;
    seg.init(H);
    query.clear();
    query.resize(n);
    lin.resize(n);
    add.assign(n, 0);
    for(int i = 0; i < q; i++){
        int j = seg.argmax(L[i]+1, R[i]+1);
        // cerr << j << "\n";
        query[j].emplace_back(L[i], R[i], i);
    }
    int root = seg.argmax(1, n);
    vector<ll> ans = solve(n, q, root);
    reverse(H.begin(), H.end());
    for(int i = 0; i < q; i++){
        int l = L[i];
        L[i] = n-1-R[i];
        R[i] = n-1-l;
    }
    for(int i = 0; i < n-i; i++){
        swap(lc[i], lc[n-1-i]);
        swap(rc[i], rc[n-1-i]);
        swap(query[i], query[n-1-i]);
    }
    for(int i = 0; i < n; i++){
        swap(lc[i], rc[i]);
        if(lc[i] != -1) lc[i] = n-1-lc[i];
        if(rc[i] != -1) rc[i] = n-1-rc[i];
        for(auto& [l, r, ind] : query[i]){
            int temp = l;
            l = n-1-r;
            r = n-1-temp;
        }
    }
    vector<ll> ans2 = solve(n, q, n-1-root);
    vector<ll> C(q);
    for(int i = 0; i < q; i++) C[i] = min(ans[i], ans2[i]);//, cerr << ans[i] << " " << ans2[i] << "\n";
	return C;
}

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