oj.uz

Submission #1099647

# Submission time Handle Problem Language Result Execution time Memory
1099647 2024-10-11T23:58:24 Z azberjibiou Meetings (IOI18_meetings) C++17
60 / 100
 4187 ms 786432 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;
 
void seg_init(int idx, int s, int 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;
    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!=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;
    int mid=(s+e)/2;
    if(pos<=mid) add(2*idx, s, mid, pos, x);
    else add(2*idx+1, mid+1, e, 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;
    }
    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 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;
    int mid=(s+e)/2;
    if(pos<=mid) del(2*idx, s, mid, pos, x);
    else del(2*idx+1, mid+1, e, pos, x);
}
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();
    seg_init(1, 1, N);
}
void solv_query(){
    for(int i=0;i<Q;i++) ans[i]=INF;
    seg_init(1, 1, N);
 
    //가장 높은 곳에서 시작
    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';
 
    //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, 1, N, 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, 1, N, rdep[i]-dr[x]+1, rdep[i], i)-rval[hmax]+(e-hmax+1)*H[hmax]);
        }
        //pop
        del(1, 1, N, rdep[i], i);
    }
 
    init_sweep();
 
    swp_typ='l';
    //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, 1, N, 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, 1, N, ldep[i]-dl[x]+1, ldep[i], i)-lval[hmax]+(hmax-s+1)*H[hmax]);
        }
        //pop
        del(1, 1, N, ldep[i], i);
    }
 
    //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<Q;i++){
        auto [s, e]=qry[i];
        int now=s;
        int hmax=mh[i];
        while(r[now]!=-1 && r[now]<=e){
            ans[i]=min(ans[i], rdp[now]+(now-s+1)*H[now]+rval[r[now]]-rval[hmax]+(e-hmax+1)*H[hmax]);
            now=r[now];
        }
        ans[i]=min(ans[i], H[now]*(e-s+1));
        now=e;
        while(l[now]!=-1 && l[now]>=s){
            ans[i]=min(ans[i], ldp[now]+(e-now+1)*H[now]+lval[l[now]]-lval[hmax]+(hmax-s+1)*H[hmax]);
            now=l[now];
        }
    }
    */
    //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

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 147216 KB Output is correct
2 Correct 78 ms 148572 KB Output is correct
3 Correct 80 ms 148612 KB Output is correct
4 Correct 67 ms 148572 KB Output is correct
5 Correct 67 ms 148572 KB Output is correct
6 Correct 66 ms 148564 KB Output is correct
7 Correct 67 ms 148568 KB Output is correct
8 Correct 66 ms 148564 KB Output is correct
9 Correct 66 ms 148372 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 147216 KB Output is correct
2 Correct 78 ms 148572 KB Output is correct
3 Correct 80 ms 148612 KB Output is correct
4 Correct 67 ms 148572 KB Output is correct
5 Correct 67 ms 148572 KB Output is correct
6 Correct 66 ms 148564 KB Output is correct
7 Correct 67 ms 148568 KB Output is correct
8 Correct 66 ms 148564 KB Output is correct
9 Correct 66 ms 148372 KB Output is correct
10 Correct 75 ms 149748 KB Output is correct
11 Correct 76 ms 149684 KB Output is correct
12 Correct 74 ms 149712 KB Output is correct
13 Correct 73 ms 149680 KB Output is correct
14 Correct 73 ms 149592 KB Output is correct
15 Correct 76 ms 149428 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 147280 KB Output is correct
2 Correct 127 ms 153320 KB Output is correct
3 Correct 411 ms 203460 KB Output is correct
4 Correct 338 ms 196940 KB Output is correct
5 Correct 328 ms 204104 KB Output is correct
6 Correct 338 ms 207752 KB Output is correct
7 Correct 379 ms 204952 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 147280 KB Output is correct
2 Correct 127 ms 153320 KB Output is correct
3 Correct 411 ms 203460 KB Output is correct
4 Correct 338 ms 196940 KB Output is correct
5 Correct 328 ms 204104 KB Output is correct
6 Correct 338 ms 207752 KB Output is correct
7 Correct 379 ms 204952 KB Output is correct
8 Correct 414 ms 206240 KB Output is correct
9 Correct 361 ms 205168 KB Output is correct
10 Correct 377 ms 207732 KB Output is correct
11 Correct 418 ms 204348 KB Output is correct
12 Correct 378 ms 203060 KB Output is correct
13 Correct 408 ms 205648 KB Output is correct
14 Correct 393 ms 202452 KB Output is correct
15 Correct 344 ms 195824 KB Output is correct
16 Correct 359 ms 207980 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 147216 KB Output is correct
2 Correct 78 ms 148572 KB Output is correct
3 Correct 80 ms 148612 KB Output is correct
4 Correct 67 ms 148572 KB Output is correct
5 Correct 67 ms 148572 KB Output is correct
6 Correct 66 ms 148564 KB Output is correct
7 Correct 67 ms 148568 KB Output is correct
8 Correct 66 ms 148564 KB Output is correct
9 Correct 66 ms 148372 KB Output is correct
10 Correct 75 ms 149748 KB Output is correct
11 Correct 76 ms 149684 KB Output is correct
12 Correct 74 ms 149712 KB Output is correct
13 Correct 73 ms 149680 KB Output is correct
14 Correct 73 ms 149592 KB Output is correct
15 Correct 76 ms 149428 KB Output is correct
16 Correct 77 ms 147280 KB Output is correct
17 Correct 127 ms 153320 KB Output is correct
18 Correct 411 ms 203460 KB Output is correct
19 Correct 338 ms 196940 KB Output is correct
20 Correct 328 ms 204104 KB Output is correct
21 Correct 338 ms 207752 KB Output is correct
22 Correct 379 ms 204952 KB Output is correct
23 Correct 414 ms 206240 KB Output is correct
24 Correct 361 ms 205168 KB Output is correct
25 Correct 377 ms 207732 KB Output is correct
26 Correct 418 ms 204348 KB Output is correct
27 Correct 378 ms 203060 KB Output is correct
28 Correct 408 ms 205648 KB Output is correct
29 Correct 393 ms 202452 KB Output is correct
30 Correct 344 ms 195824 KB Output is correct
31 Correct 359 ms 207980 KB Output is correct
32 Correct 3102 ms 634844 KB Output is correct
33 Correct 2669 ms 625632 KB Output is correct
34 Correct 3533 ms 643028 KB Output is correct
35 Correct 3304 ms 644192 KB Output is correct
36 Correct 2678 ms 635384 KB Output is correct
37 Correct 3627 ms 651896 KB Output is correct
38 Correct 4062 ms 592968 KB Output is correct
39 Correct 4187 ms 642368 KB Output is correct
40 Runtime error 2405 ms 786432 KB Execution killed with signal 9
41 Halted 0 ms 0 KB -