Submission #92480

#	Time	Username	Problem	Language	Result	Execution time	Memory
92480		Retro3014	Meetings (IOI18_meetings)	C++17	19 / 100	4410 ms	7280 KiB

meetings

#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 / 4
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40