oj.uz

Submission #1100162

# Submission time Handle Problem Language Result Execution time Memory
1100162 2024-10-13T07:44:28 Z azberjibiou Meetings (IOI18_meetings) C++17
100 / 100
 4290 ms 508564 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[2*mxN];
pii sgrng[2*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(idx+1, s, mid);
    seg_init(idx+2*(mid-s+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-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 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++, 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;
    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(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 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++, 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++) 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 22 ms 127828 KB Output is correct
2 Correct 25 ms 132188 KB Output is correct
3 Correct 25 ms 132228 KB Output is correct
4 Correct 29 ms 132252 KB Output is correct
5 Correct 27 ms 132180 KB Output is correct
6 Correct 25 ms 132464 KB Output is correct
7 Correct 27 ms 128152 KB Output is correct
8 Correct 25 ms 130580 KB Output is correct
9 Correct 24 ms 132384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 127828 KB Output is correct
2 Correct 25 ms 132188 KB Output is correct
3 Correct 25 ms 132228 KB Output is correct
4 Correct 29 ms 132252 KB Output is correct
5 Correct 27 ms 132180 KB Output is correct
6 Correct 25 ms 132464 KB Output is correct
7 Correct 27 ms 128152 KB Output is correct
8 Correct 25 ms 130580 KB Output is correct
9 Correct 24 ms 132384 KB Output is correct
10 Correct 30 ms 132532 KB Output is correct
11 Correct 29 ms 132524 KB Output is correct
12 Correct 29 ms 132532 KB Output is correct
13 Correct 41 ms 132524 KB Output is correct
14 Correct 36 ms 133120 KB Output is correct
15 Correct 28 ms 132532 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 127828 KB Output is correct
2 Correct 62 ms 137464 KB Output is correct
3 Correct 245 ms 176120 KB Output is correct
4 Correct 205 ms 160336 KB Output is correct
5 Correct 200 ms 173376 KB Output is correct
6 Correct 233 ms 181608 KB Output is correct
7 Correct 260 ms 185064 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 127828 KB Output is correct
2 Correct 62 ms 137464 KB Output is correct
3 Correct 245 ms 176120 KB Output is correct
4 Correct 205 ms 160336 KB Output is correct
5 Correct 200 ms 173376 KB Output is correct
6 Correct 233 ms 181608 KB Output is correct
7 Correct 260 ms 185064 KB Output is correct
8 Correct 244 ms 162668 KB Output is correct
9 Correct 194 ms 161556 KB Output is correct
10 Correct 237 ms 163976 KB Output is correct
11 Correct 262 ms 170984 KB Output is correct
12 Correct 202 ms 170844 KB Output is correct
13 Correct 238 ms 170840 KB Output is correct
14 Correct 265 ms 176268 KB Output is correct
15 Correct 170 ms 171076 KB Output is correct
16 Correct 242 ms 170224 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 127828 KB Output is correct
2 Correct 25 ms 132188 KB Output is correct
3 Correct 25 ms 132228 KB Output is correct
4 Correct 29 ms 132252 KB Output is correct
5 Correct 27 ms 132180 KB Output is correct
6 Correct 25 ms 132464 KB Output is correct
7 Correct 27 ms 128152 KB Output is correct
8 Correct 25 ms 130580 KB Output is correct
9 Correct 24 ms 132384 KB Output is correct
10 Correct 30 ms 132532 KB Output is correct
11 Correct 29 ms 132524 KB Output is correct
12 Correct 29 ms 132532 KB Output is correct
13 Correct 41 ms 132524 KB Output is correct
14 Correct 36 ms 133120 KB Output is correct
15 Correct 28 ms 132532 KB Output is correct
16 Correct 22 ms 127828 KB Output is correct
17 Correct 62 ms 137464 KB Output is correct
18 Correct 245 ms 176120 KB Output is correct
19 Correct 205 ms 160336 KB Output is correct
20 Correct 200 ms 173376 KB Output is correct
21 Correct 233 ms 181608 KB Output is correct
22 Correct 260 ms 185064 KB Output is correct
23 Correct 244 ms 162668 KB Output is correct
24 Correct 194 ms 161556 KB Output is correct
25 Correct 237 ms 163976 KB Output is correct
26 Correct 262 ms 170984 KB Output is correct
27 Correct 202 ms 170844 KB Output is correct
28 Correct 238 ms 170840 KB Output is correct
29 Correct 265 ms 176268 KB Output is correct
30 Correct 170 ms 171076 KB Output is correct
31 Correct 242 ms 170224 KB Output is correct
32 Correct 1878 ms 383156 KB Output is correct
33 Correct 1211 ms 383304 KB Output is correct
34 Correct 1920 ms 381168 KB Output is correct
35 Correct 2005 ms 378328 KB Output is correct
36 Correct 1417 ms 378332 KB Output is correct
37 Correct 2250 ms 378328 KB Output is correct
38 Correct 3556 ms 435404 KB Output is correct
39 Correct 3039 ms 484700 KB Output is correct
40 Correct 2401 ms 383248 KB Output is correct
41 Correct 3064 ms 505644 KB Output is correct
42 Correct 3659 ms 508564 KB Output is correct
43 Correct 4053 ms 508528 KB Output is correct
44 Correct 4290 ms 420880 KB Output is correct