Submission #702486

#	Time	Username	Problem	Language	Result	Execution time	Memory
702486		qwerasdfzxcl	Meetings (IOI18_meetings)	C++17	0 / 100	139 ms	146028 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

constexpr int MAXN = 100100;
constexpr ll INF = 4e18;

int n, q;
int a[MAXN], L[MAXN], R[MAXN], C[MAXN];
vector<int> Q[MAXN];
ll ans[MAXN];

struct Seg{
    pair<int, int> tree[MAXN*2];
    int sz;
    void init(int n, int a[]){
        sz = n;
        for (int i=sz;i<sz*2;i++) tree[i] = {a[i-sz], i-sz};
        for (int i=sz-1;i;i--) tree[i] = max(tree[i<<1], tree[i<<1|1]);
    }
    int query(int l, int r){
        ++r;
        pair<int, int> ret = {-1, -1};
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1) ret = max(ret, tree[l++]);
            if (r&1) ret = max(ret, tree[--r]);
        }

        assert(ret.second!=-1);
        return ret.second;
    }
}tree, tree2;

struct Line{
    ll a, b;
    Line(){}
    Line(ll _a, ll _b): a(_a), b(_b) {}

    ll operator()(ll x){return a*x + b;}
};

ll cross(const Line &f, const Line &g){
    assert(f.a > g.a);
    ll ret = (g.b - f.b) / (f.a - g.a) + 1;
    assert(ret <= n+1);
    return ret;
}

struct DS{
    deque<Line> L;
    deque<int> p;
    ll ofs;

    void clear(){L.clear(); p.clear(); ofs = 0;}

    void init(int x, int y){
        assert(L.empty() && p.empty() && ofs==0);
        L.emplace_back(0, y);
        p.push_back(x);
        p.push_back(x+1);
    }

    void push_front(ll a, ll b, int x){
        L.emplace_front(a, b-ofs);
        p.push_front(x);
    }

    void push_back(ll a, ll b, int x){
        L.emplace_back(a, b-ofs);
        p.push_back(x);
    }

    void add(ll x){ofs += x;}

    void insert(ll a, ll b){
        int s = p.front(); p.pop_front();
        int e = p.back();
        int prv = s;
        Line f(a, b-ofs);

        while(!L.empty()){
            if (f(p.front()-1) > L.front()(p.front()-1)){
                p.push_front(max((ll)prv, cross(f, L.front())));
                p.push_front(s);

                L.push_front(f);

                return;
            }

            prv = p.front();
            L.pop_front(); p.pop_front();
        }

        assert(L.empty() && p.empty());
        L.push_front(f);
        p.push_front(e);
        p.push_front(s);
    }

    ll back(){return L.back()(p.back()) + ofs;}
    int size(){return L.size();}

    ll operator()(int x){
        assert(p.front()<=x && x<p.back());
        int idx = upper_bound(p.begin(), p.end(), x) - p.begin() - 1;
        return L[idx](x) + ofs;
    }
}D[MAXN];

void merge(int x, int y){
    assert(D[x].p.back() + 1 == D[y].p.front());
    if (D[x].size() >= D[y].size()){
        int sz = D[y].size();
        for (int i=0;i<sz;i++){
            D[x].push_back(D[y].L[i].a, D[y].L[i].b + D[y].ofs, D[y].p[i+1]);
        }
    }
    else{
        swap(D[x], D[y]);
        D[x].p.front()--;
        int sz = D[y].size();
        for (int i=sz-1;i>=0;i--){
            D[x].push_front(D[y].L[i].a, D[y].L[i].b + D[y].ofs, D[y].p[i]);
        }
    }
}

void dnc(int l, int r){
    if (l>r) return;
    //printf("dnc: %d %d\n", l, r);

    int m = tree.query(l, r);
    dnc(l, m-1); dnc(m+1, r);

    for (auto &i:Q[m]){
        assert(L[i] <= m);

        if (m < R[i]) ans[i] = min(ans[i], D[m+1](R[i]) + (ll)a[m] * (m-L[i]+1));
        else if (m == R[i]) ans[i] = min(ans[i], (ll)a[m] * (m-L[i]+1));
        else assert(0);
    }

    if (l==r){
        D[l].init(l, a[l]);
    }
    else if (m==r){
        D[l].push_back(0, D[l].back() + a[m], m+1);
    }
    else if (l==m){
        D[m+1].add((ll)a[m] * (m-l+1));
        D[m+1].insert(a[m], - (ll)a[m]*(m-1));
        D[m+1].p.front()--;

        assert(D[m+1].p.front()==m);
        swap(D[m], D[m+1]);
    }
    else{
        ll t = D[l].back();

        D[m+1].add((ll)a[m] * (m-l+1));
        D[m+1].insert(a[m], t - (ll)a[m]*(m-1));
        merge(l, m+1);
    }

    //printf("end: %d %d\n", l, r);
}

int cnt;
void dnc0(int l, int r){
    if (l>r) return;
    //printf("dnc0: %d %d\n", l, r);

    int m = tree.query(l, r);
    C[m] = cnt--;
    dnc0(l, m-1); dnc0(m+1, r);
}

void solve(vector<int> H, vector<int> _L, vector<int> _R){
    for (int i=1;i<=n;i++){
        a[i] = H[i-1];
        Q[i].clear();
        D[i].clear();
    }

    for (int i=1;i<=q;i++){
        L[i] = _L[i-1] + 1;
        R[i] = _R[i-1] + 1;
    }

    tree.init(n+1, a);
    cnt = n;
    dnc0(1, n);
    tree2.init(n+1, C);

    for (int i=1;i<=q;i++){
        Q[tree2.query(L[i], R[i])].push_back(i);
    }

    dnc(1, n);
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
    n = H.size();
    q = L.size();
    fill(ans+1, ans+q+1, INF);

    solve(H, L, R);

    reverse(H.begin(), H.end());
    for (auto &x:L) x = n-1-x;
    for (auto &x:R) x = n-1-x;
    solve(H, R, L);

    vector<ll> rans;
    for (int i=1;i<=q;i++) rans.push_back(ans[i]);
    return rans;
}

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