oj.uz

Submission #1099703

# Submission time Handle Problem Language Result Execution time Memory
1099703 2024-10-12T03:59:38 Z azberjibiou Meetings (IOI18_meetings) C++17
100 / 100
 5008 ms 555576 KB 
#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;
vector <Node> seg[4*mxN];
pii sgrng[4*mxN];
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);
    seg[idx].resize(e-s+2);
    seg[idx][0].rlink=0;
    for(int i=1;i<=e-s+1;i++) seg[idx][i].llink=seg[idx][i].rlink=-1;
    seg[idx][0].llink=0;
    if(s==e) return;
    int mid=(s+e)/2;
    seg_init(2*idx, s, mid);
    seg_init(2*idx+1, mid+1, e);
}
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!=0) 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=-1;
    if(ln!=0 && rn!=0) add_swp(idx, ln, rn);
}
void add(int pos, int x){
    int idx=1, s=2, e=(swp_typ=='r' ? mxrdep : mxldep);
    while(true){
        add_node(idx, seg[idx][0].llink, pos-s+1, 0, x);
        if(s==e) break;
        int mid=(s+e)/2;
        if(pos<=mid) idx=2*idx, e=mid;
        else idx=2*idx+1, s=mid+1;
    }
}
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][0].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;
    }
    int mid=(s1+e1)/2;
    return min(seg_solv(2*idx, s1, mid, s2, e2, x), seg_solv(2*idx+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 bk=seg[idx][0].llink;
        if(seg[idx][bk].val==x && bk!=0) del_node(idx, bk);
        if(s==e) break;
        int mid=(s+e)/2;
        if(pos<=mid) idx=2*idx, e=mid;
        else idx=2*idx+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<4*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;
    
    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
        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(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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 147308 KB Output is correct
2 Correct 65 ms 147800 KB Output is correct
3 Correct 64 ms 147808 KB Output is correct
4 Correct 74 ms 147812 KB Output is correct
5 Correct 77 ms 147808 KB Output is correct
6 Correct 78 ms 148044 KB Output is correct
7 Correct 86 ms 147744 KB Output is correct
8 Correct 71 ms 148208 KB Output is correct
9 Correct 72 ms 148004 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 147308 KB Output is correct
2 Correct 65 ms 147800 KB Output is correct
3 Correct 64 ms 147808 KB Output is correct
4 Correct 74 ms 147812 KB Output is correct
5 Correct 77 ms 147808 KB Output is correct
6 Correct 78 ms 148044 KB Output is correct
7 Correct 86 ms 147744 KB Output is correct
8 Correct 71 ms 148208 KB Output is correct
9 Correct 72 ms 148004 KB Output is correct
10 Correct 78 ms 148408 KB Output is correct
11 Correct 78 ms 148412 KB Output is correct
12 Correct 78 ms 148624 KB Output is correct
13 Correct 68 ms 148568 KB Output is correct
14 Correct 68 ms 149112 KB Output is correct
15 Correct 69 ms 148400 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 147276 KB Output is correct
2 Correct 114 ms 152804 KB Output is correct
3 Correct 317 ms 188876 KB Output is correct
4 Correct 240 ms 170924 KB Output is correct
5 Correct 264 ms 189528 KB Output is correct
6 Correct 270 ms 194152 KB Output is correct
7 Correct 342 ms 196800 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 147276 KB Output is correct
2 Correct 114 ms 152804 KB Output is correct
3 Correct 317 ms 188876 KB Output is correct
4 Correct 240 ms 170924 KB Output is correct
5 Correct 264 ms 189528 KB Output is correct
6 Correct 270 ms 194152 KB Output is correct
7 Correct 342 ms 196800 KB Output is correct
8 Correct 301 ms 175976 KB Output is correct
9 Correct 231 ms 174616 KB Output is correct
10 Correct 247 ms 177160 KB Output is correct
11 Correct 331 ms 183996 KB Output is correct
12 Correct 224 ms 184020 KB Output is correct
13 Correct 257 ms 184080 KB Output is correct
14 Correct 282 ms 187828 KB Output is correct
15 Correct 183 ms 184132 KB Output is correct
16 Correct 278 ms 183412 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 147308 KB Output is correct
2 Correct 65 ms 147800 KB Output is correct
3 Correct 64 ms 147808 KB Output is correct
4 Correct 74 ms 147812 KB Output is correct
5 Correct 77 ms 147808 KB Output is correct
6 Correct 78 ms 148044 KB Output is correct
7 Correct 86 ms 147744 KB Output is correct
8 Correct 71 ms 148208 KB Output is correct
9 Correct 72 ms 148004 KB Output is correct
10 Correct 78 ms 148408 KB Output is correct
11 Correct 78 ms 148412 KB Output is correct
12 Correct 78 ms 148624 KB Output is correct
13 Correct 68 ms 148568 KB Output is correct
14 Correct 68 ms 149112 KB Output is correct
15 Correct 69 ms 148400 KB Output is correct
16 Correct 71 ms 147276 KB Output is correct
17 Correct 114 ms 152804 KB Output is correct
18 Correct 317 ms 188876 KB Output is correct
19 Correct 240 ms 170924 KB Output is correct
20 Correct 264 ms 189528 KB Output is correct
21 Correct 270 ms 194152 KB Output is correct
22 Correct 342 ms 196800 KB Output is correct
23 Correct 301 ms 175976 KB Output is correct
24 Correct 231 ms 174616 KB Output is correct
25 Correct 247 ms 177160 KB Output is correct
26 Correct 331 ms 183996 KB Output is correct
27 Correct 224 ms 184020 KB Output is correct
28 Correct 257 ms 184080 KB Output is correct
29 Correct 282 ms 187828 KB Output is correct
30 Correct 183 ms 184132 KB Output is correct
31 Correct 278 ms 183412 KB Output is correct
32 Correct 2005 ms 430052 KB Output is correct
33 Correct 1462 ms 430200 KB Output is correct
34 Correct 2155 ms 427972 KB Output is correct
35 Correct 2095 ms 409332 KB Output is correct
36 Correct 1385 ms 409328 KB Output is correct
37 Correct 2415 ms 409332 KB Output is correct
38 Correct 3636 ms 473648 KB Output is correct
39 Correct 3702 ms 518004 KB Output is correct
40 Correct 2844 ms 430136 KB Output is correct
41 Correct 3273 ms 552360 KB Output is correct
42 Correct 5008 ms 554768 KB Output is correct
43 Correct 4273 ms 555576 KB Output is correct
44 Correct 4596 ms 466668 KB Output is correct