oj.uz

Submission #92487

# Submission time Handle Problem Language Result Execution time Memory
92487 2019-01-03T05:47:28 Z Retro3014 Meetings (IOI18_meetings) C++17
60 / 100
 4333 ms 176756 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;
        v.resize(N);
        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();}
        v.clear();
        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;
            if(!vv.empty()) 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;
            if(!vv.empty()) 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 793 ms 484 KB Output is correct
3 Correct 793 ms 504 KB Output is correct
4 Correct 802 ms 484 KB Output is correct
5 Correct 798 ms 504 KB Output is correct
6 Correct 795 ms 504 KB Output is correct
7 Correct 801 ms 472 KB Output is correct
8 Correct 793 ms 480 KB Output is correct
9 Correct 805 ms 472 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 793 ms 484 KB Output is correct
3 Correct 793 ms 504 KB Output is correct
4 Correct 802 ms 484 KB Output is correct
5 Correct 798 ms 504 KB Output is correct
6 Correct 795 ms 504 KB Output is correct
7 Correct 801 ms 472 KB Output is correct
8 Correct 793 ms 480 KB Output is correct
9 Correct 805 ms 472 KB Output is correct
10 Correct 3346 ms 692 KB Output is correct
11 Correct 4284 ms 736 KB Output is correct
12 Correct 3314 ms 700 KB Output is correct
13 Correct 4333 ms 700 KB Output is correct
14 Correct 3380 ms 696 KB Output is correct
15 Correct 3376 ms 732 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 40 ms 4496 KB Output is correct
3 Correct 220 ms 45824 KB Output is correct
4 Correct 237 ms 45816 KB Output is correct
5 Correct 196 ms 45956 KB Output is correct
6 Correct 214 ms 45960 KB Output is correct
7 Correct 216 ms 46040 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 40 ms 4496 KB Output is correct
3 Correct 220 ms 45824 KB Output is correct
4 Correct 237 ms 45816 KB Output is correct
5 Correct 196 ms 45956 KB Output is correct
6 Correct 214 ms 45960 KB Output is correct
7 Correct 216 ms 46040 KB Output is correct
8 Correct 278 ms 45752 KB Output is correct
9 Correct 190 ms 45812 KB Output is correct
10 Correct 224 ms 45820 KB Output is correct
11 Correct 246 ms 45764 KB Output is correct
12 Correct 197 ms 45804 KB Output is correct
13 Correct 236 ms 45736 KB Output is correct
14 Correct 178 ms 45740 KB Output is correct
15 Correct 311 ms 45832 KB Output is correct
16 Correct 218 ms 45936 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 793 ms 484 KB Output is correct
3 Correct 793 ms 504 KB Output is correct
4 Correct 802 ms 484 KB Output is correct
5 Correct 798 ms 504 KB Output is correct
6 Correct 795 ms 504 KB Output is correct
7 Correct 801 ms 472 KB Output is correct
8 Correct 793 ms 480 KB Output is correct
9 Correct 805 ms 472 KB Output is correct
10 Correct 3346 ms 692 KB Output is correct
11 Correct 4284 ms 736 KB Output is correct
12 Correct 3314 ms 700 KB Output is correct
13 Correct 4333 ms 700 KB Output is correct
14 Correct 3380 ms 696 KB Output is correct
15 Correct 3376 ms 732 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 40 ms 4496 KB Output is correct
18 Correct 220 ms 45824 KB Output is correct
19 Correct 237 ms 45816 KB Output is correct
20 Correct 196 ms 45956 KB Output is correct
21 Correct 214 ms 45960 KB Output is correct
22 Correct 216 ms 46040 KB Output is correct
23 Correct 278 ms 45752 KB Output is correct
24 Correct 190 ms 45812 KB Output is correct
25 Correct 224 ms 45820 KB Output is correct
26 Correct 246 ms 45764 KB Output is correct
27 Correct 197 ms 45804 KB Output is correct
28 Correct 236 ms 45736 KB Output is correct
29 Correct 178 ms 45740 KB Output is correct
30 Correct 311 ms 45832 KB Output is correct
31 Correct 218 ms 45936 KB Output is correct
32 Runtime error 588 ms 176756 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Halted 0 ms 0 KB -