oj.uz

Submission #1099697

# Submission time Handle Problem Language Result Execution time Memory
1099697 2024-10-12T03:37:11 Z azberjibiou Meetings (IOI18_meetings) C++17
100 / 100
 4562 ms 716516 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();
}
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 swap_f(event t);
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) swap_f(event(idx, lv, rv));
        else if(itx<=N-1) swp[itx].emplace_back(idx, lv, rv);
    }
    else{
        if(itx>=now_x) swap_f(event(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(), sgrng[i]=pii();
    for(int i=0;i<mxN;i++) swp[i].clear();
    imswp.clear();
    now_x=0;
    for(int i=0;i<mxN;i++) ppct[i].clear(), qct[i].clear();
}
void solv_query(){
    for(int i=0;i<Q;i++) ans[i]=INF;
    int mxrdep=2, mxldep=2;
    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(1, 2, mxrdep, 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(1, 2, mxrdep, 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(1, 2, mxldep, 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(1, 2, mxldep, 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();   
}
*/

Compilation message

meetings.cpp: In function 'void add_node(int, int, int, int, int)':
meetings.cpp:216:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  216 |     if(rn!=seg[idx].size()-1) add_swp(idx, now, rn);
      |        ~~^~~~~~~~~~~~~~~~~~~
meetings.cpp: In function 'void del_node(int, int)':
meetings.cpp:224:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |     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 43 ms 148308 KB Output is correct
2 Correct 45 ms 148828 KB Output is correct
3 Correct 46 ms 148828 KB Output is correct
4 Correct 46 ms 148768 KB Output is correct
5 Correct 46 ms 149012 KB Output is correct
6 Correct 59 ms 149052 KB Output is correct
7 Correct 45 ms 148824 KB Output is correct
8 Correct 45 ms 149012 KB Output is correct
9 Correct 45 ms 149092 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 148308 KB Output is correct
2 Correct 45 ms 148828 KB Output is correct
3 Correct 46 ms 148828 KB Output is correct
4 Correct 46 ms 148768 KB Output is correct
5 Correct 46 ms 149012 KB Output is correct
6 Correct 59 ms 149052 KB Output is correct
7 Correct 45 ms 148824 KB Output is correct
8 Correct 45 ms 149012 KB Output is correct
9 Correct 45 ms 149092 KB Output is correct
10 Correct 58 ms 149684 KB Output is correct
11 Correct 56 ms 149520 KB Output is correct
12 Correct 56 ms 149460 KB Output is correct
13 Correct 58 ms 149424 KB Output is correct
14 Correct 59 ms 150080 KB Output is correct
15 Correct 55 ms 149548 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 148288 KB Output is correct
2 Correct 94 ms 153148 KB Output is correct
3 Correct 298 ms 183176 KB Output is correct
4 Correct 223 ms 182320 KB Output is correct
5 Correct 226 ms 182964 KB Output is correct
6 Correct 251 ms 183564 KB Output is correct
7 Correct 292 ms 188572 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 148288 KB Output is correct
2 Correct 94 ms 153148 KB Output is correct
3 Correct 298 ms 183176 KB Output is correct
4 Correct 223 ms 182320 KB Output is correct
5 Correct 226 ms 182964 KB Output is correct
6 Correct 251 ms 183564 KB Output is correct
7 Correct 292 ms 188572 KB Output is correct
8 Correct 272 ms 182388 KB Output is correct
9 Correct 212 ms 182388 KB Output is correct
10 Correct 253 ms 182388 KB Output is correct
11 Correct 228 ms 182364 KB Output is correct
12 Correct 192 ms 182344 KB Output is correct
13 Correct 209 ms 182340 KB Output is correct
14 Correct 302 ms 182736 KB Output is correct
15 Correct 184 ms 182520 KB Output is correct
16 Correct 278 ms 186992 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 148308 KB Output is correct
2 Correct 45 ms 148828 KB Output is correct
3 Correct 46 ms 148828 KB Output is correct
4 Correct 46 ms 148768 KB Output is correct
5 Correct 46 ms 149012 KB Output is correct
6 Correct 59 ms 149052 KB Output is correct
7 Correct 45 ms 148824 KB Output is correct
8 Correct 45 ms 149012 KB Output is correct
9 Correct 45 ms 149092 KB Output is correct
10 Correct 58 ms 149684 KB Output is correct
11 Correct 56 ms 149520 KB Output is correct
12 Correct 56 ms 149460 KB Output is correct
13 Correct 58 ms 149424 KB Output is correct
14 Correct 59 ms 150080 KB Output is correct
15 Correct 55 ms 149548 KB Output is correct
16 Correct 50 ms 148288 KB Output is correct
17 Correct 94 ms 153148 KB Output is correct
18 Correct 298 ms 183176 KB Output is correct
19 Correct 223 ms 182320 KB Output is correct
20 Correct 226 ms 182964 KB Output is correct
21 Correct 251 ms 183564 KB Output is correct
22 Correct 292 ms 188572 KB Output is correct
23 Correct 272 ms 182388 KB Output is correct
24 Correct 212 ms 182388 KB Output is correct
25 Correct 253 ms 182388 KB Output is correct
26 Correct 228 ms 182364 KB Output is correct
27 Correct 192 ms 182344 KB Output is correct
28 Correct 209 ms 182340 KB Output is correct
29 Correct 302 ms 182736 KB Output is correct
30 Correct 184 ms 182520 KB Output is correct
31 Correct 278 ms 186992 KB Output is correct
32 Correct 1786 ms 411504 KB Output is correct
33 Correct 1098 ms 411556 KB Output is correct
34 Correct 2031 ms 409304 KB Output is correct
35 Correct 2119 ms 411372 KB Output is correct
36 Correct 1374 ms 411572 KB Output is correct
37 Correct 1913 ms 409324 KB Output is correct
38 Correct 3472 ms 427588 KB Output is correct
39 Correct 3674 ms 422748 KB Output is correct
40 Correct 2603 ms 411560 KB Output is correct
41 Correct 3710 ms 699612 KB Output is correct
42 Correct 4562 ms 711480 KB Output is correct
43 Correct 4061 ms 716516 KB Output is correct
44 Correct 4359 ms 573448 KB Output is correct