Submission #702518

#	Time	Username	Problem	Language	Result	Execution time	Memory
702518		qwerasdfzxcl	Meetings (IOI18_meetings)	C++17	100 / 100	1833 ms	315756 KiB

meetings

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

using namespace std;
typedef long long ll;

constexpr int MAXN = 750750;
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;
    bool inv;
    void init(int n, int a[], bool INV){
        inv = INV;
        sz = n;
        for (int i=sz;i<sz*2;i++) tree[i] = {a[i-sz], inv?(sz-i):(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, 0};
        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);
        return inv?-ret.second: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;
}

template<typename T>
struct Deque{
    vector<T> a;
    int s, e, sz;

    Deque(){s = e = sz = 0;}

    void resize(){
        if (a.empty()) a.resize(2);
        else{
            vector<T> b(a.size()*2);
            int j = 0;
            for (int i=s;i!=e;i++,j++){
                if (i==(int)a.size()) i = 0;
                if (i==e) break;
                b[j] = a[i];
            }

            swap(a, b);
            s = 0;
            e = j;
        }
    }

    void push_front(T x){
        if (sz>=(int)a.size()-1) resize();
        --s;
        if (s<0) s = (int)a.size()-1;
        a[s] = x;

        ++sz;
    }

    void push_back(T x){
        if (sz>=(int)a.size()-1) resize();
        a[e] = x;
        e++;
        if (e==(int)a.size()) e = 0;

        ++sz;
    }

    void pop_front(){
        s++;
        if (s==(int)a.size()) s = 0;

        --sz;
    }

    T front(){return a[s];}
    void frontd(){a[s]--;}

    T back(){
        if (!e) return a.back();
        return a[e-1];
    }

    T operator [](int x){
        if (s+x<(int)a.size()) return a[s+x];
        return a[s+x-(int)a.size()];
    }

    int size(){return sz;}

    bool empty(){return sz == 0;}

    void clear(){a.clear(); s = e = sz = 0;}
};

int _search(Deque<int> &dq, int target){
    int l = 0, r = (int)dq.size()-1, ret = dq.size();

    while(l<=r){
        int m = (l+r)>>1;
        if (target < dq[m]) r = m-1, ret = m;
        else l = m+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.push_back(Line(0, y));
        p.push_back(x);
        p.push_back(x+1);
    }

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

    void push_back(ll a, ll b, int x){
        L.push_back(Line(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()-1) + ofs;}
    int size(){return L.size();}

    ll operator()(int x){
        assert(p.front()<=x && x<p.back());
        int idx = _search(p, x) - 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.frontd();
        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;

    int m = tree.query(l, r);
    //printf("dnc: %d %d (mid = %d)\n", l, r, m);
    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.frontd();

        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("\nDS %d %d (mid = %d)\n", l, r, m);
    for (int i=0;i<D[l].L.size();i++) {auto [a, b] = D[l].L[i]; printf(" (%lld, %lld)", a, b+D[l].ofs);}
    printf("\n");
    for (int i=0;i<D[l].p.size();i++) printf(" %d", D[l].p[i]);
    printf("\n");

    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, bool INV){
    /*printf("-------------------------------\n");
    for (auto &x:H) printf(" %d", x);
    printf("\n");*/

    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, INV);
    cnt = n;
    dnc0(1, n);
    tree2.init(n+1, C, INV);

    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, 0);

    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, 1);

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

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