oj.uz

Submission #1099649

# Submission time Handle Problem Language Result Execution time Memory
1099649 2024-10-12T00:14:05 Z azberjibiou Meetings (IOI18_meetings) C++17
60 / 100
 4178 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=750500;
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 74 ms 147384 KB Output is correct
2 Correct 76 ms 148572 KB Output is correct
3 Correct 79 ms 148568 KB Output is correct
4 Correct 84 ms 148568 KB Output is correct
5 Correct 68 ms 148568 KB Output is correct
6 Correct 76 ms 148568 KB Output is correct
7 Correct 83 ms 148572 KB Output is correct
8 Correct 76 ms 148760 KB Output is correct
9 Correct 79 ms 148508 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 147384 KB Output is correct
2 Correct 76 ms 148572 KB Output is correct
3 Correct 79 ms 148568 KB Output is correct
4 Correct 84 ms 148568 KB Output is correct
5 Correct 68 ms 148568 KB Output is correct
6 Correct 76 ms 148568 KB Output is correct
7 Correct 83 ms 148572 KB Output is correct
8 Correct 76 ms 148760 KB Output is correct
9 Correct 79 ms 148508 KB Output is correct
10 Correct 84 ms 149936 KB Output is correct
11 Correct 86 ms 149768 KB Output is correct
12 Correct 87 ms 149864 KB Output is correct
13 Correct 84 ms 150192 KB Output is correct
14 Correct 82 ms 149756 KB Output is correct
15 Correct 89 ms 149460 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 147280 KB Output is correct
2 Correct 129 ms 153308 KB Output is correct
3 Correct 389 ms 203728 KB Output is correct
4 Correct 340 ms 197192 KB Output is correct
5 Correct 287 ms 204204 KB Output is correct
6 Correct 300 ms 207592 KB Output is correct
7 Correct 334 ms 204984 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 147280 KB Output is correct
2 Correct 129 ms 153308 KB Output is correct
3 Correct 389 ms 203728 KB Output is correct
4 Correct 340 ms 197192 KB Output is correct
5 Correct 287 ms 204204 KB Output is correct
6 Correct 300 ms 207592 KB Output is correct
7 Correct 334 ms 204984 KB Output is correct
8 Correct 372 ms 206428 KB Output is correct
9 Correct 319 ms 205164 KB Output is correct
10 Correct 404 ms 207696 KB Output is correct
11 Correct 391 ms 204364 KB Output is correct
12 Correct 349 ms 203348 KB Output is correct
13 Correct 411 ms 205904 KB Output is correct
14 Correct 399 ms 202188 KB Output is correct
15 Correct 364 ms 195856 KB Output is correct
16 Correct 380 ms 207988 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 147384 KB Output is correct
2 Correct 76 ms 148572 KB Output is correct
3 Correct 79 ms 148568 KB Output is correct
4 Correct 84 ms 148568 KB Output is correct
5 Correct 68 ms 148568 KB Output is correct
6 Correct 76 ms 148568 KB Output is correct
7 Correct 83 ms 148572 KB Output is correct
8 Correct 76 ms 148760 KB Output is correct
9 Correct 79 ms 148508 KB Output is correct
10 Correct 84 ms 149936 KB Output is correct
11 Correct 86 ms 149768 KB Output is correct
12 Correct 87 ms 149864 KB Output is correct
13 Correct 84 ms 150192 KB Output is correct
14 Correct 82 ms 149756 KB Output is correct
15 Correct 89 ms 149460 KB Output is correct
16 Correct 72 ms 147280 KB Output is correct
17 Correct 129 ms 153308 KB Output is correct
18 Correct 389 ms 203728 KB Output is correct
19 Correct 340 ms 197192 KB Output is correct
20 Correct 287 ms 204204 KB Output is correct
21 Correct 300 ms 207592 KB Output is correct
22 Correct 334 ms 204984 KB Output is correct
23 Correct 372 ms 206428 KB Output is correct
24 Correct 319 ms 205164 KB Output is correct
25 Correct 404 ms 207696 KB Output is correct
26 Correct 391 ms 204364 KB Output is correct
27 Correct 349 ms 203348 KB Output is correct
28 Correct 411 ms 205904 KB Output is correct
29 Correct 399 ms 202188 KB Output is correct
30 Correct 364 ms 195856 KB Output is correct
31 Correct 380 ms 207988 KB Output is correct
32 Correct 3353 ms 635036 KB Output is correct
33 Correct 2530 ms 625888 KB Output is correct
34 Correct 3613 ms 643140 KB Output is correct
35 Correct 3292 ms 644408 KB Output is correct
36 Correct 2754 ms 635484 KB Output is correct
37 Correct 3648 ms 651932 KB Output is correct
38 Correct 4178 ms 593100 KB Output is correct
39 Correct 3996 ms 642400 KB Output is correct
40 Runtime error 3019 ms 786432 KB Execution killed with signal 9
41 Halted 0 ms 0 KB -