Submission #1100300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100300		azberjibiou	Meetings (IOI18_meetings)	C++17	100 / 100	4105 ms	696592 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=750005;
const int mxM=2200005;
const int mxK=61;
const int MOD=1e9+7;
const ll INF=1e18;
int N, Q;
ll H[mxN];
pii qry[mxN];
ll l[mxN], r[mxN];
ll ldp[mxN], rdp[mxN]; // ldp[i] : [l[i]+1, i]에서 시작점을 선택해서 [l[i]+1, i-1]에 대한 최소 비용
ll rval[mxN], lval[mxN];
int ldep[mxN], rdep[mxN];
int dl[mxN], dr[mxN], mh[mxN];
pii lrng[mxN], rrng[mxN];
pll rline[mxN], lline[mxN];
ll ans[mxN];
void init(vector <int> h, vector <int> L, vector <int> R){
    N=h.size();
    for(int i=0;i<N;i++) H[i]=h[i];
    Q=L.size();
    for(int i=0;i<Q;i++) qry[i]=pii(L[i], R[i]);
}
 
void input(){
    cin >> N >> Q;
    for(int i=0;i<N;i++) cin >> H[i];
    for(int i=0;i<Q;i++) cin >> qry[i].fi >> qry[i].se;
}
 
void make_cartesian_tree(){ // 두 산의 높이가 같으면 오른쪽에 있는 산의 높이가 더 높다
    stack <int> stk;
    for(int i=0;i<N;i++){
        while(stk.size() && H[stk.top()]<=H[i]) stk.pop();
        if(stk.size()) l[i]=stk.top();
        else l[i]=-1;
        stk.push(i);
    }
    while(stk.size()) stk.pop();
    for(int i=N-1;i>=0;i--){
        while(stk.size() && H[stk.top()]<H[i]) stk.pop();
        if(stk.size()) r[i]=stk.top();
        else r[i]=-1;
        stk.push(i);
    }
    //dep
    for(int i=0;i<N;i++){
        if(l[i]==-1) ldep[i]=1;
        else ldep[i]=ldep[l[i]]+1;
    }
    for(int i=N-1;i>=0;i--){
        if(r[i]==-1) rdep[i]=1;
        else rdep[i]=rdep[r[i]]+1;
    }
    //rng
    for(int i=0;i<N;i++){
        if(l[i]==-1) rrng[i]=pii(0, i);
        else rrng[i]=pii(l[i]+1, i);
        if(r[i]==-1) lrng[i]=pii(i, N-1);
        else lrng[i]=pii(i, r[i]-1);
    }
}
void make_dp(){
    //길이 2짜리 segment의 비용은 0이다
    vector <pii> v;
    for(int i=0;i<N;i++){
        if(l[i]!=-1 && r[i]!=-1) v.emplace_back(max(i-l[i], r[i]-i), i);
    }
    sort(all(v));
    for(auto [d, i] : v){
        if(H[l[i]]<=H[r[i]]){
            int now=l[i];
            rdp[now]=min(rdp[i]+(i-l[i])*H[i], ldp[i]+(r[i]-i)*H[i]);
        }
        else{
            int now=r[i];
            ldp[now]=min(rdp[i]+(i-l[i])*H[i], ldp[i]+(r[i]-i)*H[i]);
        }
    }
}
void make_lrval(){
    for(int i=N-1;i>=0;i--){
        if(r[i]==-1) rval[i]=(N-i)*H[i];
        else rval[i]=(r[i]-i)*H[i]+rval[r[i]];
    }
    for(int i=0;i<N;i++){
        if(l[i]==-1) lval[i]=(i+1)*H[i];
        else lval[i]=(i-l[i])*H[i]+lval[l[i]];
    }
}
void make_sps(){
    vector <vector <int>> spsl(N, vector<int>(20)), spsr(N, vector<int>(20));
    for(int j=0;j<N;j++){
        spsl[j][0]=l[j];
        spsr[j][0]=r[j];
    }
    for(int i=1;i<20;i++){
        for(int j=0;j<N;j++){
            if(spsl[j][i-1]==-1 || spsl[spsl[j][i-1]][i-1]==-1) spsl[j][i]=-1;
            else spsl[j][i]=spsl[spsl[j][i-1]][i-1];
            if(spsr[j][i-1]==-1 || spsr[spsr[j][i-1]][i-1]==-1) spsr[j][i]=-1;
            else spsr[j][i]=spsr[spsr[j][i-1]][i-1];
        }
    }
    for(int i=0;i<Q;i++){
        auto [s, e]=qry[i];
        int now=s;
        for(int j=19;j>=0;j--){
            if(spsr[now][j]!=-1 && spsr[now][j]<=e) dr[i]+=(1<<j), now=spsr[now][j];
        }
        now=e;
        for(int j=19;j>=0;j--){
            if(spsl[now][j]!=-1 && spsl[now][j]>=s) dl[i]+=(1<<j), now=spsl[now][j];
        }
        mh[i]=now;
    }
    spsl.clear(); spsr.clear();
    spsl.shrink_to_fit(); spsr.shrink_to_fit();
}
void make_line(){
    //rdp[now]+(now-s+1)*H[now]+rval[r[now]]-rval[hmax]+(e-hmax+1)*H[hmax] : y = -H[now]*x + rdp[now]+(now+1)*H[now]+rval[r[now]]에 -rval[hmax]+(e-hmax+1)*H[hmax]를 더한다
    //ldp[now]+(e-now+1)*H[now]+lval[l[now]]-lval[hmax]+(hmax-s+1)*H[hmax] : y = H[now]*x + ldp[now]+(-now+1)*H[now]+lval[l[now]]에 -lval[hmax]+(hmax-s+1)*H[hmax]를 더한다
    for(int i=0;i<N;i++){
        if(l[i]!=-1) lline[i]=pll(H[i], ldp[i]+(-i+1)*H[i]+lval[l[i]]);
        else lline[i]=pll();
        if(r[i]!=-1) rline[i]=pll(-H[i], rdp[i]+(i+1)*H[i]+rval[r[i]]);
        else rline[i]=pll();
    }
}
struct Node{
    int val;
    int llink, rlink;
    Node() : val(), llink(), rlink() {}
    Node(int val, int llink, int rlink) : val(val), llink(llink), rlink(rlink) {}
};
struct event{
    int idx;
    int e1, e2;
    event() : idx(), e1(), e2() {}
    event(int idx, int e1, int e2) : idx(idx), e1(e1), e2(e2) {}
};
char swp_typ;
Node seg[mxN*21];
pii sgrng[2*mxN];
int sgidx[2*mxN];
int idxs;
vector <event> swp[mxN], imswp; // imswp means immediate swap, where intersection <= x 
int now_x;
int mxrdep=2, mxldep=2;
 
void seg_init(int idx, int s, int e){
    sgrng[idx]=pii(s, e);
    sgidx[idx]=idxs;
    idxs+=e-s+2;
    int ni=sgidx[idx];
    seg[ni].llink=seg[ni].rlink=ni;
    for(int i=1;i<=e-s+1;i++) seg[ni+i].llink=seg[ni+i].rlink=-1;
    if(s==e) return;
    int mid=(s+e)/2;
    seg_init(idx+1, s, mid);
    seg_init(idx+2*(mid-s+1), mid+1, e);
}
ll intersection(int e1, int e2){
    pll c1, c2;
    if(swp_typ=='r') c1=rline[e1], c2=rline[e2];
    else c1=lline[e1], c2=lline[e2];
    if(swp_typ=='r') assert(c1.fi<=c2.fi);
    else assert(c1.fi>=c2.fi);
    if(c1.fi==c2.fi){
        if(c1.se<=c2.se) return (swp_typ=='r' ? 0 : N);
        else return (swp_typ=='r' ? N+1 : -1);
    }
    if(swp_typ=='r'){
        pll c3=pll(c1.fi-c2.fi, c1.se-c2.se);
        if(c3.se<=0) return -1;
        return (c3.se-1)/(-c3.fi)+1;
    }
    else{
        pll c3=pll(c2.fi-c1.fi, c2.se-c1.se);
        if(c3.se<=0) return -1;
        return c3.se/(-c3.fi);
    }
 
} // e1이 e2보다 작아지는 순간을 리턴
void del_node(int idx, int now);
void add_swp(int idx, int ln, int rn){
    int lv=seg[ln].val, rv=seg[rn].val;
    ll itx=intersection(lv, rv);
    if(swp_typ=='r'){
        if(itx<=now_x){
            del_node(idx, rdep[rv]-sgrng[idx].fi+1);
        }
        else if(itx<=N-1) swp[itx].emplace_back(idx, lv, rv);
    }
    else{
        if(itx>=now_x){
            del_node(idx, ldep[rv]-sgrng[idx].fi+1);
        }
        else if(itx>=0) swp[itx].emplace_back(idx, lv, rv);
    }
}
void add_node(int idx, int ln, int now, int rn, int x){
    int ni=sgidx[idx];
    seg[ni+now].rlink=rn+ni;
    seg[ni+now].llink=ln+ni;
    seg[ni+ln].rlink=now+ni;
    seg[ni+rn].llink=now+ni;
    seg[ni+now].val=x;
    if(ln!=0) add_swp(idx, ln+ni, now+ni);
    if(rn!=0) add_swp(idx, now+ni, rn+ni);
}
void del_node(int idx, int now){
    int ni=sgidx[idx];
    int ln=seg[ni+now].llink, rn=seg[ni+now].rlink;
    seg[ln].rlink=rn;
    seg[rn].llink=ln;
    seg[ni+now].llink=seg[ni+now].rlink=-1;
    if(ln!=ni && rn!=ni) add_swp(idx, ln, rn);
}
void add(int pos, int x){
    int idx=1, s=2, e=(swp_typ=='r' ? mxrdep : mxldep);
    while(true){
        int ni=sgidx[idx];
        add_node(idx, seg[ni].llink-ni, pos-s+1, 0, x);
        if(s==e) break;
        int mid=(s+e)/2;
        if(pos<=mid) idx++, e=mid;
        else idx+=2*(mid-s+1), s=mid+1;
    }
}
void swap_f(event t){
    auto [idx, e1, e2]=t;
    int s=sgrng[idx].fi, ni=sgidx[idx];
    int idx1=(swp_typ=='r' ? rdep[e1] : ldep[e1])-s+1, idx2=(swp_typ=='r' ? rdep[e2] : ldep[e2])-s+1;
    if(seg[ni+idx1].rlink==ni+idx2 && seg[ni+idx2].llink==ni+idx1 && seg[ni+idx1].val==e1 && seg[ni+idx2].val==e2){
        del_node(idx, idx2);
    }
}
ll seg_solv(int idx, int s1, int e1, int s2, int e2, ll x){
    if(s2>e1 || s1>e2) return INF;
    if(s2<=s1 && e1<=e2){
        int ni=sgidx[idx];
        int bk=seg[ni].llink;
        if(bk==ni) return INF;
        pll ln=(swp_typ=='r' ? rline[seg[bk].val] : lline[seg[bk].val]);
        return ln.fi*x+ln.se;
    }
    int mid=(s1+e1)/2;
    return min(seg_solv(idx+1, s1, mid, s2, e2, x), seg_solv(idx+2*(mid-s1+1), mid+1, e1, s2, e2, x));
}
void del(int pos, int x){
    int idx=1, s=2, e=(swp_typ=='r' ? mxrdep : mxldep);
    while(true){
        int ni=sgidx[idx];
        int bk=seg[ni].llink;
        if(seg[bk].val==x && bk!=ni) del_node(idx, bk-ni);
        if(s==e) break;
        int mid=(s+e)/2;
        if(pos<=mid) idx++, e=mid;
        else idx+=2*(mid-s+1), s=mid+1;
    }
}
vector <int> ppct[mxN]; // i번 직선을 push하면 i, pop하면 -i-1
vector <int> qct[mxN];
 
void init_sweep(){
    for(int i=0;i<2*mxN;i++) sgrng[i]=pii();
    for(int i=0;i<mxN;i++) swp[i].clear();
    imswp.clear();
    now_x=0;
    for(int i=0;i<mxN;i++) ppct[i].clear(), qct[i].clear();
    idxs=0;
}
void solv_query(){
    for(int i=0;i<Q;i++) ans[i]=INF;
    
    for(int i=0;i<N;i++){
        if(l[i]!=-1) mxldep=max(mxldep, ldep[i]);
        if(r[i]!=-1) mxrdep=max(mxrdep, rdep[i]);
    }
    //가장 높은 곳에서 시작
    for(int i=0;i<Q;i++) ans[i]=min(ans[i], (qry[i].se-qry[i].fi+1)*H[mh[i]]);
    
    swp_typ='r';
 
    seg_init(1, 2, mxrdep);
    //dpr에 대해서 segment tree sweeping
    for(int i=N-1;i>=0;i--){ // 깊이가 낮은 것부터 push -> i--
        if(r[i]==-1) continue;
        ppct[rrng[i].fi].push_back(i);
    }
    // i에 대해서 push -> 쿼리 시행 -> i가 끝나면 i를 pop
    for(int i=0;i<Q;i++) qct[qry[i].fi].push_back(i);
    for(int i=0;i<N;i++){
        now_x=i;
        //add element
        for(int x : ppct[i]){ // add element
            add(rdep[x], x);
        }
        //maintain list
        for(event t : swp[i]) swap_f(t);
        swp[i].clear();
        //solve queries
        for(int x : qct[i]){ 
            int e=qry[x].se;
            int hmax=mh[x];
            if(dr[x]>=1) ans[x]=min(ans[x], seg_solv(1, 2, mxrdep, rdep[i]-dr[x]+1, rdep[i], i)-rval[hmax]+(e-hmax+1)*H[hmax]);
        }
        //pop
        del(rdep[i], i);
    }
    init_sweep();
 
    
    swp_typ='l';
 
    seg_init(1, 2, mxldep);
 
    //dpl에 대해서 segment tree sweeping
    for(int i=0;i<N;i++){ // 깊이가 낮은 것부터 push -> i++
        if(l[i]==-1) continue;
        ppct[lrng[i].se].push_back(i);
    }
    // i에 대해서 push -> 쿼리 시행 -> i가 끝나면 i를 pop
    for(int i=0;i<Q;i++) qct[qry[i].se].push_back(i);
    for(int i=N-1;i>=0;i--){
        now_x=i;
        //add element
        for(int x : ppct[i]){ // add element
            add(ldep[x], x);
        }
        //maintain list
        while(swp[i].size() || imswp.size()){
            if(swp[i].size()){
                event t=swp[i].back();
                swp[i].pop_back();
                swap_f(t);
            }
            else{
                event t=imswp.back();
                imswp.pop_back();
                swap_f(t);
            }
        }
        //solve queries
        for(int x : qct[i]){ 
            int s=qry[x].fi;
            int hmax=mh[x];
            if(dl[x]>=1) ans[x]=min(ans[x], seg_solv(1, 2, mxldep, ldep[i]-dl[x]+1, ldep[i], i)-lval[hmax]+(hmax-s+1)*H[hmax]);
        }
        //pop
        del(ldep[i], i);
    }
    //for(int i=0;i<Q;i++) cout << ans[i] << '\n';
}
void solv(){
    make_cartesian_tree();
    make_dp();
    make_lrval();
    make_sps();
    make_line();
    solv_query();
}
vector<ll> minimum_costs(vector<int> h, vector<int> L, vector<int> R) {
    init(h, L, R);
    solv();
    vector <ll> C(Q);
    for(int j=0;j<Q;j++) C[j]=ans[j];
    return C;
}
/*
int main()
{
    gibon
    input();
    solv();   
}
*/

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