oj.uz

Submission #1099644

# Submission time Handle Problem Language Result Execution time Memory
1099644 2024-10-11T22:52:58 Z azberjibiou Meetings (IOI18_meetings) C++17
21 / 100
 417 ms 210036 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)-1);
    }
 
} // 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 73 ms 147284 KB Output is correct
2 Correct 77 ms 148572 KB Output is correct
3 Correct 77 ms 148496 KB Output is correct
4 Correct 78 ms 148572 KB Output is correct
5 Correct 76 ms 148572 KB Output is correct
6 Correct 75 ms 148356 KB Output is correct
7 Correct 75 ms 148540 KB Output is correct
8 Correct 78 ms 148504 KB Output is correct
9 Correct 77 ms 148456 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 147284 KB Output is correct
2 Correct 77 ms 148572 KB Output is correct
3 Correct 77 ms 148496 KB Output is correct
4 Correct 78 ms 148572 KB Output is correct
5 Correct 76 ms 148572 KB Output is correct
6 Correct 75 ms 148356 KB Output is correct
7 Correct 75 ms 148540 KB Output is correct
8 Correct 78 ms 148504 KB Output is correct
9 Correct 77 ms 148456 KB Output is correct
10 Correct 83 ms 150072 KB Output is correct
11 Correct 88 ms 149940 KB Output is correct
12 Incorrect 86 ms 149944 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 147284 KB Output is correct
2 Correct 120 ms 153744 KB Output is correct
3 Correct 384 ms 205612 KB Output is correct
4 Correct 383 ms 198984 KB Output is correct
5 Correct 322 ms 206020 KB Output is correct
6 Correct 307 ms 209392 KB Output is correct
7 Correct 376 ms 206920 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 147284 KB Output is correct
2 Correct 120 ms 153744 KB Output is correct
3 Correct 384 ms 205612 KB Output is correct
4 Correct 383 ms 198984 KB Output is correct
5 Correct 322 ms 206020 KB Output is correct
6 Correct 307 ms 209392 KB Output is correct
7 Correct 376 ms 206920 KB Output is correct
8 Incorrect 417 ms 210036 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 147284 KB Output is correct
2 Correct 77 ms 148572 KB Output is correct
3 Correct 77 ms 148496 KB Output is correct
4 Correct 78 ms 148572 KB Output is correct
5 Correct 76 ms 148572 KB Output is correct
6 Correct 75 ms 148356 KB Output is correct
7 Correct 75 ms 148540 KB Output is correct
8 Correct 78 ms 148504 KB Output is correct
9 Correct 77 ms 148456 KB Output is correct
10 Correct 83 ms 150072 KB Output is correct
11 Correct 88 ms 149940 KB Output is correct
12 Incorrect 86 ms 149944 KB Output isn't correct
13 Halted 0 ms 0 KB -