제출 #597710

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
597710		Lucpp	모임들 (IOI18_meetings)	C++17	0 / 100	1 ms	340 KiB

meetings

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

struct Seg{
    int cap;
    vector<pair<int, int>> seg;
    void init(vector<int> 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<int, 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<int> 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]){
        if(R > i){
            answer[ind] = H[i]*(i+1-L);
            answer[ind] += add[rc[i]] + get(R);
        }
        else{
            answer[ind] = H[i]+add[lc[i]]+get(R-1);
        }
    }
    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);
        lin[i] = {0, 0};
        add[i] = add[rc[i]]+H[i];
    }
    else{
        s.emplace(i, i);
        auto it = s.lower_bound({i+1, 0});
        lin[i] = {H[i]+get(i-1), 0};
        ll le = lin[i].a + add[lc[i]];
        int until = end;
        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(it->first <= j && j <= r);
                lin[j] = lin[it->first];
                s.erase(it);
                s.emplace(j, r);
                until = j-1;
                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, vector<int> L, vector<int> R){
    s.clear();
    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);
    }
    answer.assign(q, 0);
    calc(seg.argmax(1, n), 0, n-1);
	return answer;
}

vector<ll> minimum_costs(vector<int> h, vector<int> L, vector<int> R){
    H = h;
    int n = sz(H);
    int q = sz(L);
    vector<ll> ans = solve(n, q, L, R);
    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;
    }
    vector<ll> ans2 = solve(n, q, L, R);
    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: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40