oj.uz

Submission #92486

# Submission time Handle Problem Language Result Execution time Memory
92486 2019-01-03T05:42:58 Z Retro3014 Meetings (IOI18_meetings) C++17
19 / 100
 4370 ms 92248 KB 
#include "meetings.h"
#include <vector>

using namespace std;
#define MAX_N 5000
#define INF 1000000000000000000LL
typedef long long ll;

int N, Q;
int seg1[MAX_N*4+1];
ll seg2[MAX_N*4+1];
int two=1;

void update1(int x, int y){
    x+=two; while(x>0)  {seg1[x]=max(seg1[x], y); x/=2;}
}
void update2(int x, ll y){
    x+=two; while(x>0){seg2[x]+=y; x/=2;}
}
int maxi(int x, int y){
    x+=two; y+=two;
    int ret=0;
    while(x<=y){
        if(x==y)    return max(ret, seg1[x]);
        if(x%2) ret=max(ret, seg1[x++]);
        if(!(y%2))ret=max(ret, seg1[y--]);
        x/=2; y/=2;
    }return ret;
}

ll sum(int x, int y){
    x+=two; y+=two;
    ll ret=0;
    while(x<=y){
        if(x==y)    return ret+seg2[x];
        if(x%2) ret+=seg2[x++];
        if(!(y%2))ret+=seg2[y--];
        x/=2; y/=2;
    }return ret;
}

#define MAX_N2 100001
vector<int> v;
int Li[MAX_N2+1], Ri[MAX_N2+1];
ll seg[21][MAX_N2*4+1];

void update(int h, int x, ll y){
    x+=two; while(x>0)  {seg[h][x]=min(seg[h][x], y); x/=2;}
}

ll min(int h, int x, int y){
    x+=two; y+=two; ll ret=INF;
    while(x<=y){
        if(x==y)    return min(ret, seg[h][x]);
        if(x%2) ret=min(ret, seg[h][x++]);
        if(!(y%2)) ret=min(ret, seg[h][y--]);
        x/=2; y/=2;
    }return ret;
}


vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    N=(int)H.size(); Q=(int)L.size();
    vector<ll> C(Q);
    //*
    if(N<=5000 && Q<=5000){
        for(int i=0; i<Q; i++)  C[i]=INF;
        while(two<N)   two*=2;
        for(int i=0; i<N; i++)  update1(i, H[i]);
        for(int i=0; i<N; i++){
            for(int j=1; j<two*2; j++){
                seg2[j]=0;
            }
            for(int j=0; j<N; j++){
                update2(j, maxi(min(i, j), max(i, j)));
            }
            for(int j=0; j<Q; j++){
                if(i>=L[j] && i<=R[j])  C[j]=min(C[j], sum(L[j], R[j]));
            }
        }
    }else{//*/
        while(two<N)   two*=2;
        for(int h=1; h<=20; h++)    for(int i=1; i<two*2; i++)  seg[h][i]=INF;
        for(int i=0; i<N; i++){
            while(!v.empty() && H[v.back()]<H[i]){
                Ri[v.back()]=i; v.pop_back();
            }v.push_back(i);
        }while(!v.empty())  {Ri[v.back()]=N; v.pop_back();}
        for(int i=N-1; i>=0; i--){
            while(!v.empty() && H[v.back()]<H[i]){
                Li[v.back()]=i; v.pop_back();
            }v.push_back(i);
        }while(!v.empty()){Li[v.back()]=-1; v.pop_back();}
        int l, r;ll d=0;
        for(int i=0; i<N; i++){
            l=Li[i]; r=Ri[i]; d=(ll)(Ri[i]-Li[i]-1)*(ll)H[i];
            for(int h=H[i]; h<=20; h++){
                if(l!=-1 && H[l]==h){
                    d+=(ll)h*(l-Li[l]); l=Li[l];
                }
                if(r!=N && H[r]==h){
                    d+=(ll)h*(Ri[r]-r); r=Ri[r];
                }
                update(h, i, d+(ll)(1+l)*h+(ll)(N-r)*h);
            }
        }
        int Hl, Hr;
        vector<int> vv;
        for(int i=0; i<Q; i++){
            C[i]=INF;
            l=L[i]; r=R[i];
            while(Ri[l]<=R[i]) {vv.push_back(l);l=Ri[l];}
            Hl=l;
            ll RL=0;
            RL = (ll)(H[Hl]-H[vv.back()])*(R[i]-Hl+1);
            while(!vv.empty()){
                l=vv.back(); vv.pop_back();
                C[i]=min(C[i], min(H[l], l, Ri[l]-1)-(ll)L[i]*H[l]-(ll)H[l]*(N-R[i]-1)+RL);
                if(!vv.empty()) RL+=(ll)(R[i]-l+1)*(H[l]-H[vv.back()]);
            }
            while(Li[r]>=L[i])    {vv.push_back(r);r=Li[r];}
            Hr=r;
            RL = (ll)(H[Hr]-H[vv.back()])*(Hr-L[i]+1);
            while(!vv.empty()){
                r=vv.back(); vv.pop_back();
                C[i]=min(C[i], min(H[r], Li[r]+1, r)-(ll)(N-R[i]-1)*H[r]-(ll)H[r]*L[i]+RL);
                if(!vv.empty()) RL += (ll) (r-L[i]+1)*(H[r]-H[vv.back()]);
            }
            C[i]=min(C[i], min(H[Hl], Hl, Hr)-(ll)H[Hl]*(L[i]+N-R[i]-1));
        }
    }
    return C;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 816 ms 476 KB Output is correct
3 Correct 815 ms 476 KB Output is correct
4 Correct 822 ms 504 KB Output is correct
5 Correct 816 ms 480 KB Output is correct
6 Correct 816 ms 480 KB Output is correct
7 Correct 832 ms 476 KB Output is correct
8 Correct 826 ms 468 KB Output is correct
9 Correct 815 ms 476 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 816 ms 476 KB Output is correct
3 Correct 815 ms 476 KB Output is correct
4 Correct 822 ms 504 KB Output is correct
5 Correct 816 ms 480 KB Output is correct
6 Correct 816 ms 480 KB Output is correct
7 Correct 832 ms 476 KB Output is correct
8 Correct 826 ms 468 KB Output is correct
9 Correct 815 ms 476 KB Output is correct
10 Correct 3446 ms 700 KB Output is correct
11 Correct 4370 ms 700 KB Output is correct
12 Correct 3376 ms 700 KB Output is correct
13 Correct 4342 ms 692 KB Output is correct
14 Correct 3403 ms 700 KB Output is correct
15 Correct 3393 ms 700 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 39 ms 4428 KB Output is correct
3 Runtime error 243 ms 92248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 39 ms 4428 KB Output is correct
3 Runtime error 243 ms 92248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 816 ms 476 KB Output is correct
3 Correct 815 ms 476 KB Output is correct
4 Correct 822 ms 504 KB Output is correct
5 Correct 816 ms 480 KB Output is correct
6 Correct 816 ms 480 KB Output is correct
7 Correct 832 ms 476 KB Output is correct
8 Correct 826 ms 468 KB Output is correct
9 Correct 815 ms 476 KB Output is correct
10 Correct 3446 ms 700 KB Output is correct
11 Correct 4370 ms 700 KB Output is correct
12 Correct 3376 ms 700 KB Output is correct
13 Correct 4342 ms 692 KB Output is correct
14 Correct 3403 ms 700 KB Output is correct
15 Correct 3393 ms 700 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 39 ms 4428 KB Output is correct
18 Runtime error 243 ms 92248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -