Submission #1103573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103573		azberjibiou	Meetings (IOI18_meetings)	C++17	100 / 100	4239 ms	364824 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;
const int B=20;
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];
        }
    }
  	for(int i=1;i<20;i++){
    	for(int j=0;j<N;j++){
            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];
        }
    }
  	for(int i=0;i<Q;i++){
      	auto [s, e]=qry[i];
        int 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;
vector <Node> seg[2*mxN];
pii sgrng[2*mxN];
vector <event> swp[mxN], imswp; // imswp means immediate swap, where intersection <= x 
int now_x;
 
void seg_init(int idx, int s, int e){
    //printf("(%d, %d, %d)\n", idx, s, e);
    sgrng[idx]=pii(s, e);
    seg[idx].resize(e-s+3);
    seg[idx][0].rlink=e-s+2;
    for(int i=1;i<=e-s+1;i++) seg[idx][i].llink=seg[idx][i].rlink=-1;
    seg[idx][e-s+2].llink=0;
    if(s==e) return;
    if(e-s<=B-1){
        for(int i=0;i<=e-s;i++) seg_init(idx+i+1, s+i, s+i);
        return;
    }
    int mid[B];
    for(int i=0;i<B;i++) mid[i]=((B-1-i)*s+(i+1)*e)/B;
    seg_init(idx+1, s, mid[0]);
    for(int i=0;i<B-1;i++) seg_init(idx+2*(mid[i]-s+1), mid[i]+1, mid[i+1]);
}
ll intersection(int e1, int e2){
    //printf("swp_typ=%c\n", swp_typ);
    //printf("e1=%d, e2=%d\n", e1, 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%(-c3.fi)==0 ? c3.se/(-c3.fi) : c3.se/(-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)==0 ? c3.se/(-c3.fi) : c3.se/(-c3.fi));
    }
 
} // e1이 e2보다 작아지는 순간을 리턴
void add_swp(int idx, int ln, int rn){
    int lv=seg[idx][ln].val, rv=seg[idx][rn].val;
    ll itx=intersection(lv, rv);
    if(swp_typ=='r'){
        if(itx<=now_x) imswp.emplace_back(idx, lv, rv);
        else if(itx<=N-1) swp[itx].emplace_back(idx, lv, rv);
    }
    else{
        if(itx>=now_x) imswp.emplace_back(idx, lv, rv);
        else if(itx>=0) swp[itx].emplace_back(idx, lv, rv);
    }
}
void add_node(int idx, int ln, int now, int rn, int x){
    //printf("add: ");
    //printf("idx=%d, ln, now, rn, x=%d %d %d %d\n", idx, ln, now, rn, x);
    seg[idx][now].rlink=rn;
    seg[idx][now].llink=ln;
    seg[idx][ln].rlink=now;
    seg[idx][rn].llink=now;
    seg[idx][now].val=x;
    if(ln!=0) add_swp(idx, ln, now);
    if(rn!=seg[idx].size()-1) add_swp(idx, now, rn);
}
void del_node(int idx, int now){
    //printf("del: idx, now = %d %d\n", idx, now);
    int ln=seg[idx][now].llink, rn=seg[idx][now].rlink;
    seg[idx][ln].rlink=rn;
    seg[idx][rn].llink=ln;
    seg[idx][now].llink=seg[idx][now].rlink=seg[idx][now].val=-1;
    if(ln!=0 && rn!=seg[idx].size()-1) add_swp(idx, ln, rn);
}
void add(int idx, int s, int e, int pos, int x){
    int rn=seg[idx].size()-1, ln=seg[idx][rn].llink;
    add_node(idx, ln, pos-s+1, rn, x);
    if(s==e) return;
    if(e-s<=B-1){
        for(int i=0;i<=e-s;i++) if(pos==s+i) add(idx+i+1, s+i, s+i, pos, x);
        return;
    }
    int mid[B];
    for(int i=0;i<B;i++) mid[i]=((B-1-i)*s+(i+1)*e)/B;
    if(pos<=mid[0]) add(idx+1, s, mid[0], pos, x);
    for(int i=0;i<B-1;i++) if(mid[i]<pos && pos<=mid[i+1]) add(idx+2*(mid[i]-s+1), mid[i]+1, mid[i+1], pos, x);
}
void swap_f(event t){
    auto [idx, e1, e2]=t;
    int s=sgrng[idx].fi;
    int idx1=(swp_typ=='r' ? rdep[e1] : ldep[e1])-s+1, idx2=(swp_typ=='r' ? rdep[e2] : ldep[e2])-s+1;
    if(seg[idx][idx1].rlink==idx2 && seg[idx][idx2].llink==idx1 && seg[idx][idx1].val==e1 && seg[idx][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 bk=seg[idx].back().llink;
        if(bk==0) return INF;
        pll ln=(swp_typ=='r' ? rline[seg[idx][bk].val] : lline[seg[idx][bk].val]);
        return ln.fi*x+ln.se;
    }
    ll res=INF;
    if(e1-s1<=B-1){
        for(int i=0;i<=e1-s1;i++) res=min(res, seg_solv(idx+i+1, s1+i, s1+i, s2, e2, x));
        return res;
    }
    int mid[B];
    for(int i=0;i<B;i++) mid[i]=((B-1-i)*s1+(i+1)*e1)/B;
    res=min(res, seg_solv(idx+1, s1, mid[0], s2, e2, x));
    for(int i=0;i<B-1;i++){
      if(mid[i]+1>e2 || s2>mid[i+1]) continue;
      res=min(res, seg_solv(idx+2*(mid[i]-s1+1), mid[i]+1, mid[i+1], s2, e2, x));
    } 
    return res;
}
void del(int idx, int s, int e, int pos, int x){
    int bk=seg[idx].back().llink;
    if(seg[idx][bk].val==x && bk!=0){
        del_node(idx, bk);
    }
    if(s==e) return;
    if(e-s<=B-1){
        for(int i=0;i<=e-s;i++) if(pos==s+i) del(idx+i+1, s+i, s+i, pos, x);
        return;
    }
    int mid[B];
    for(int i=0;i<B;i++) mid[i]=((B-1-i)*s+(i+1)*e)/B;
    if(pos<=mid[0]) del(idx+1, s, mid[0], pos, x);
    for(int i=0;i<B-1;i++) if(mid[i]<pos && pos<=mid[i+1]) del(idx+2*(mid[i]-s+1), mid[i]+1, mid[i+1], pos, x);
}
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++) seg[i].clear(), seg[i].shrink_to_fit(), sgrng[i]=pii();
    for(int i=0;i<mxN;i++) swp[i].clear(), swp[i].shrink_to_fit();
    imswp.clear(), imswp.shrink_to_fit();
    now_x=0;
    for(int i=0;i<mxN;i++) ppct[i].clear(), ppct[i].shrink_to_fit(), qct[i].clear(), qct[i].shrink_to_fit();
}
void solv_query(){
    for(int i=0;i<Q;i++) ans[i]=INF;
    int mxrdep=2, mxldep=2;
    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(1, 2, mxrdep, rdep[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 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(1, 2, mxrdep, 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(1, 2, mxldep, 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(1, 2, mxldep, 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();   
}
*/

Compilation message (stderr)

meetings.cpp: In function 'void add_node(int, int, int, int, int)':
meetings.cpp:229:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  229 |     if(rn!=seg[idx].size()-1) add_swp(idx, now, rn);
      |        ~~^~~~~~~~~~~~~~~~~~~
meetings.cpp: In function 'void del_node(int, int)':
meetings.cpp:237:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  237 |     if(ln!=0 && rn!=seg[idx].size()-1) add_swp(idx, ln, rn);
      |                 ~~^~~~~~~~~~~~~~~~~~~

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