oj.uz

Submission #92480

# Submission time Handle Problem Language Result Execution time Memory
92480 2019-01-03T04:09:39 Z Retro3014 Meetings (IOI18_meetings) C++17
19 / 100
 4410 ms 7280 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 100004
vector<int> v;
int Li[MAX_N2+1], Ri[MAX_N2+1];
ll seg[21][MAX_N2*4+1];
ll CL[21][MAX_N2+1], CR[21][MAX_N2+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);
            }
        }
        for(int h=1; h<=20; h++){
            for(int i=0; i<N; i++){
                if(Li[i]==-1)   CL[h][i]=(ll)(i+1)*min(h, H[i]);
                else    CL[h][i]=(ll)(i-Li[i])*min(h, H[i])+CL[h][Li[i]];
            }
            for(int i=N-1; i>0; i--){
                if(Ri[i]==N)    CR[h][i]=(ll)(N-i)*min(h, H[i]);
                else    CR[h][i]=(ll)(Ri[i]-i)*min(h, H[i])+CR[h][Ri[i]];
            }
        }
        int Hl, Hr;
        for(int i=0; i<Q; i++){
            C[i]=INF;
            l=L[i]; r=R[i];
            while(Ri[l]<=R[i]) l=Ri[l];
            Hl=l;
            while(Li[r]>=L[i])    r=Li[r];
            Hr=r;
            l=L[i]; r=R[i];
            while(Ri[l]<=R[i]){
                C[i]=min(C[i], min(H[l], l, Ri[l]-1)-CL[H[l]][L[i]-1]-CR[H[Hl]][Hl]+(ll)H[Hl]*(R[i]-Hl+1));
                l=Ri[l];
            }
            while(Li[r]>=L[i]){
                C[i]=min(C[i], min(H[l], Li[r]+1, r)-CR[H[l]][R[i]+1]-CL[H[Hr]][Hr]+(ll)H[Hr]*(Hl-L[i]+1));
                r=Li[r];
            }
            C[i]=min(C[i], min(H[Hl], Hl, Hr)-CL[H[Hl]][Li[i]-1]-CR[H[Hl]][Ri[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 832 ms 376 KB Output is correct
3 Correct 823 ms 504 KB Output is correct
4 Correct 829 ms 504 KB Output is correct
5 Correct 823 ms 504 KB Output is correct
6 Correct 825 ms 504 KB Output is correct
7 Correct 820 ms 504 KB Output is correct
8 Correct 820 ms 476 KB Output is correct
9 Correct 822 ms 480 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 832 ms 376 KB Output is correct
3 Correct 823 ms 504 KB Output is correct
4 Correct 829 ms 504 KB Output is correct
5 Correct 823 ms 504 KB Output is correct
6 Correct 825 ms 504 KB Output is correct
7 Correct 820 ms 504 KB Output is correct
8 Correct 820 ms 476 KB Output is correct
9 Correct 822 ms 480 KB Output is correct
10 Correct 3384 ms 704 KB Output is correct
11 Correct 4410 ms 704 KB Output is correct
12 Correct 3377 ms 700 KB Output is correct
13 Correct 4358 ms 708 KB Output is correct
14 Correct 3407 ms 692 KB Output is correct
15 Correct 3417 ms 704 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 42 ms 7280 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 42 ms 7280 KB Output isn't correct
3 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 832 ms 376 KB Output is correct
3 Correct 823 ms 504 KB Output is correct
4 Correct 829 ms 504 KB Output is correct
5 Correct 823 ms 504 KB Output is correct
6 Correct 825 ms 504 KB Output is correct
7 Correct 820 ms 504 KB Output is correct
8 Correct 820 ms 476 KB Output is correct
9 Correct 822 ms 480 KB Output is correct
10 Correct 3384 ms 704 KB Output is correct
11 Correct 4410 ms 704 KB Output is correct
12 Correct 3377 ms 700 KB Output is correct
13 Correct 4358 ms 708 KB Output is correct
14 Correct 3407 ms 692 KB Output is correct
15 Correct 3417 ms 704 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Incorrect 42 ms 7280 KB Output isn't correct
18 Halted 0 ms 0 KB -