oj.uz

Submission #1098808

# Submission time Handle Problem Language Result Execution time Memory
1098808 2024-10-10T03:12:09 Z azberjibiou Meetings (IOI18_meetings) C++17
36 / 100
 5500 ms 28860 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 spsl[mxN][20], spsr[mxN][20];
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);
    }
}
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(){
    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];
        }
    }
}
void solv_query(){
    for(int i=0;i<Q;i++) ans[i]=INF;
    for(int i=0;i<Q;i++){
        auto [s, e]=qry[i];
        int now=s;
        int hmax=now;
        for(int j=19;j>=0;j--){
            if(spsr[hmax][j]!=-1 && spsr[hmax][j]<=e) hmax=spsr[hmax][j];
        }
        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();
    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 0 ms 348 KB Output is correct
2 Correct 2 ms 1164 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 2 ms 1372 KB Output is correct
6 Correct 1 ms 996 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 1164 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 2 ms 1372 KB Output is correct
6 Correct 1 ms 996 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 4 ms 1884 KB Output is correct
11 Correct 3 ms 1848 KB Output is correct
12 Correct 4 ms 1880 KB Output is correct
13 Correct 6 ms 1884 KB Output is correct
14 Correct 14 ms 1904 KB Output is correct
15 Correct 3 ms 1884 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 176 ms 4180 KB Output is correct
3 Correct 4348 ms 28860 KB Output is correct
4 Correct 194 ms 28080 KB Output is correct
5 Correct 55 ms 28836 KB Output is correct
6 Correct 185 ms 27748 KB Output is correct
7 Correct 5222 ms 27560 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 176 ms 4180 KB Output is correct
3 Correct 4348 ms 28860 KB Output is correct
4 Correct 194 ms 28080 KB Output is correct
5 Correct 55 ms 28836 KB Output is correct
6 Correct 185 ms 27748 KB Output is correct
7 Correct 5222 ms 27560 KB Output is correct
8 Correct 1914 ms 28344 KB Output is correct
9 Execution timed out 5516 ms 28324 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 1164 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 2 ms 1372 KB Output is correct
6 Correct 1 ms 996 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 4 ms 1884 KB Output is correct
11 Correct 3 ms 1848 KB Output is correct
12 Correct 4 ms 1880 KB Output is correct
13 Correct 6 ms 1884 KB Output is correct
14 Correct 14 ms 1904 KB Output is correct
15 Correct 3 ms 1884 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 176 ms 4180 KB Output is correct
18 Correct 4348 ms 28860 KB Output is correct
19 Correct 194 ms 28080 KB Output is correct
20 Correct 55 ms 28836 KB Output is correct
21 Correct 185 ms 27748 KB Output is correct
22 Correct 5222 ms 27560 KB Output is correct
23 Correct 1914 ms 28344 KB Output is correct
24 Execution timed out 5516 ms 28324 KB Time limit exceeded
25 Halted 0 ms 0 KB -