Submission #1099689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099689		azberjibiou	Meetings (IOI18_meetings)	C++17	60 / 100	3755 ms	786432 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();
    }
}

int push_idx[mxN][21];
int lseg_idx[mxN][21][2], rseg_idx[mxN][21][2];
vector <int> dep_ct[21];
pii sgrng[4*mxN];
void make_push_idx(int idx, int s, int e, int d, int x){
    push_idx[x][d]=idx;
    if(s==e) return;
    int mid=(s+e)/2;
    if(x<=mid) make_push_idx(2*idx, s, mid, d+1, x);
    else make_push_idx(2*idx+1, mid+1, e, d+1, x);
}
void make_query_idx(int idx, int s1, int e1, int s2, int e2, int d, int x, char lr){
    if(s2>e1 || s1>e2) return;
    if(s2<=s1 && e1<=e2){
        if(lr=='r'){
            if(rseg_idx[x][d][0]==0) rseg_idx[x][d][0]=idx;
            else rseg_idx[x][d][1]=idx;
        }
        else{
            if(lseg_idx[x][d][0]==0) lseg_idx[x][d][0]=idx;
            else lseg_idx[x][d][1]=idx;
        }
        return;
    }
    int mid=(s1+e1)/2;
    make_query_idx(2*idx, s1, mid, s2, e2, d+1, x, lr);
    make_query_idx(2*idx+1, mid+1, e1, s2, e2, d+1, x, lr);
}
void make_seg_idx(int idx, int s, int e, int d){
    dep_ct[d].push_back(idx);
    sgrng[idx]=pii(s, e);
    if(s==e) return;
    int mid=(s+e)/2;
    make_seg_idx(2*idx, s, mid, d+1);
    make_seg_idx(2*idx+1, mid+1, e, d+1);
}
void make_idx(){
    for(int i=1;i<=N;i++){
        make_push_idx(1, 1, N, 0, i);
    }
    for(int i=0;i<Q;i++){
        if(dl[i]>=1) make_query_idx(1, 1, N, ldep[qry[i].se]-dl[i]+1, ldep[qry[i].se], 0, i, 'l');
        if(dr[i]>=1) make_query_idx(1, 1, N, rdep[qry[i].fi]-dr[i]+1, rdep[qry[i].fi], 0, i, 'r');
    }
    make_seg_idx(1, 1, N, 0);
    /*
    for(int i=1;i<=N;i++) for(int j=0;j<3;j++) printf("push_idx[%d][%d]=%d\n", i, j, push_idx[i][j]);
    for(int i=0;i<Q;i++){
        for(int j=0;j<5;j++){
            printf("lseg_idx[%d][%d]=%d %d\n", i, j, lseg_idx[i][j][0], lseg_idx[i][j][1]);
        }
    }
    for(int i=0;i<5;i++){
        printf("i=%d: ", i);
        for(int x : dep_ct[i]) printf("%d ", x);
    }
    */
}

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[4*mxN];
vector <event> swp[mxN], imswp; // imswp means immediate swap, where intersection <= x 
int now_x;


 
void seg_init(int current_depth){
    for(int x : dep_ct[current_depth]){
        auto [s, e]=sgrng[x];
        seg[x].resize(e-s+3);
        seg[x][0].rlink=e-s+2;
        seg[x][e-s+2].llink=0;
        for(int i=1;i<=e-s+1;i++) seg[x][i].rlink=seg[x][i].llink=-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 pos, int x){
    int rn=seg[idx].size()-1, ln=seg[idx][rn].llink, s=sgrng[idx].fi;
    add_node(idx, ln, pos-s+1, rn, 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, ll x){
    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;
}
void del(int idx, int x){
    int bk=seg[idx].back().llink;
    if(bk!=0 && seg[idx][bk].val==x){
        del_node(idx, bk);
    }
}
vector <int> ppct, qct;
int pidx, qidx;
 
void solv_query(){
    for(int i=0;i<Q;i++) ans[i]=INF;
 
    //가장 높은 곳에서 시작
    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';

    for(int i=0;i<N;i++) if(r[i]!=-1) ppct.push_back(i);
    for(int i=0;i<Q;i++) qct.push_back(i);
    sort(all(ppct), [&](int a, int b){return (rrng[a].fi!=rrng[b].fi ? rrng[a].fi<rrng[b].fi : a>b);});
    sort(all(qct), [&](int a, int b){return qry[a].fi<qry[b].fi;});

    for(int z=0;z<21;z++){
        seg_init(z);
        pidx=qidx=0;
        //dpr에 대해서 segment tree sweeping

        // i에 대해서 push -> 쿼리 시행 -> i가 끝나면 i를 pop
        for(int i=0;i<N;i++){
            now_x=i;
            //add element
            while(pidx!=ppct.size() && rrng[ppct[pidx]].fi==i){ // add element
                int x=ppct[pidx];
                if(push_idx[rdep[x]][z]!=0) add(push_idx[rdep[x]][z], rdep[x], x);
                pidx++;
            }
            
            //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
            while(qidx!=qct.size() && qry[qct[qidx]].fi==i){
                int x=qct[qidx];
                int e=qry[x].se;
                int hmax=mh[x];
                for(int k=0;k<=1;k++) if(rseg_idx[x][z][k]!=0) ans[x]=min(ans[x], seg_solv(rseg_idx[x][z][k], i)-rval[hmax]+(e-hmax+1)*H[hmax]);
                qidx++;
            }
            //pop
            if(push_idx[rdep[i]][z]!=0) del(push_idx[rdep[i]][z], i);
        }
    }

    
    swp_typ='l';

    ppct.clear();
    for(int i=0;i<N;i++) if(l[i]!=-1) ppct.push_back(i);
    sort(all(ppct), [&](int a, int b){return (lrng[a].se!=lrng[b].se ? lrng[a].se>lrng[b].se : a<b);});
    sort(all(qct), [&](int a, int b){return qry[a].se>qry[b].se;});

    for(int z=0;z<21;z++){
        seg_init(z);
        pidx=qidx=0;
        //dpl에 대해서 segment tree sweeping
        // i에 대해서 push -> 쿼리 시행 -> i가 끝나면 i를 pop
        for(int i=N-1;i>=0;i--){
            now_x=i;
            //add element
            while(pidx!=ppct.size() && lrng[ppct[pidx]].se==i){
                int x=ppct[pidx];
                if(push_idx[ldep[x]][z]!=0) add(push_idx[ldep[x]][z], ldep[x], x);
                pidx++;
            }
            //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
            while(qidx!=qct.size() && qry[qct[qidx]].se==i){
                int x=qct[qidx];
                int s=qry[x].fi;
                int hmax=mh[x];
                for(int k=0;k<=1;k++) if(lseg_idx[x][z][k]!=0) ans[x]=min(ans[x], seg_solv(lseg_idx[x][z][k], i)-lval[hmax]+(hmax-s+1)*H[hmax]);
                qidx++;
            }
            //pop
            if(push_idx[ldep[i]][z]!=0) del(push_idx[ldep[i]][z], 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();
    make_idx();
    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:274:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  274 |     if(rn!=seg[idx].size()-1) add_swp(idx, now, rn);
      |        ~~^~~~~~~~~~~~~~~~~~~
meetings.cpp: In function 'void del_node(int, int)':
meetings.cpp:282:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  282 |     if(ln!=0 && rn!=seg[idx].size()-1) add_swp(idx, ln, rn);
      |                 ~~^~~~~~~~~~~~~~~~~~~
meetings.cpp: In function 'void solv_query()':
meetings.cpp:334:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  334 |             while(pidx!=ppct.size() && rrng[ppct[pidx]].fi==i){ // add element
      |                   ~~~~^~~~~~~~~~~~~
meetings.cpp:354:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  354 |             while(qidx!=qct.size() && qry[qct[qidx]].fi==i){
      |                   ~~~~^~~~~~~~~~~~
meetings.cpp:382:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  382 |             while(pidx!=ppct.size() && lrng[ppct[pidx]].se==i){
      |                   ~~~~^~~~~~~~~~~~~
meetings.cpp:401:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  401 |             while(qidx!=qct.size() && qry[qct[qidx]].se==i){
      |                   ~~~~^~~~~~~~~~~~

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