oj.uz

답안 #92481

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
92481 2019-01-03T04:38:54 Z Retro3014 모임들 (IOI18_meetings) C++17
19 / 100
 4415 ms 92356 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];

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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 825 ms 508 KB Output is correct
3 Correct 820 ms 492 KB Output is correct
4 Correct 819 ms 480 KB Output is correct
5 Correct 824 ms 476 KB Output is correct
6 Correct 819 ms 488 KB Output is correct
7 Correct 832 ms 504 KB Output is correct
8 Correct 822 ms 504 KB Output is correct
9 Correct 820 ms 504 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 825 ms 508 KB Output is correct
3 Correct 820 ms 492 KB Output is correct
4 Correct 819 ms 480 KB Output is correct
5 Correct 824 ms 476 KB Output is correct
6 Correct 819 ms 488 KB Output is correct
7 Correct 832 ms 504 KB Output is correct
8 Correct 822 ms 504 KB Output is correct
9 Correct 820 ms 504 KB Output is correct
10 Correct 3457 ms 696 KB Output is correct
11 Correct 4404 ms 692 KB Output is correct
12 Correct 3400 ms 700 KB Output is correct
13 Correct 4415 ms 704 KB Output is correct
14 Correct 3416 ms 696 KB Output is correct
15 Correct 3413 ms 700 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 39 ms 4432 KB Output is correct
3 Runtime error 245 ms 92356 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 39 ms 4432 KB Output is correct
3 Runtime error 245 ms 92356 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 825 ms 508 KB Output is correct
3 Correct 820 ms 492 KB Output is correct
4 Correct 819 ms 480 KB Output is correct
5 Correct 824 ms 476 KB Output is correct
6 Correct 819 ms 488 KB Output is correct
7 Correct 832 ms 504 KB Output is correct
8 Correct 822 ms 504 KB Output is correct
9 Correct 820 ms 504 KB Output is correct
10 Correct 3457 ms 696 KB Output is correct
11 Correct 4404 ms 692 KB Output is correct
12 Correct 3400 ms 700 KB Output is correct
13 Correct 4415 ms 704 KB Output is correct
14 Correct 3416 ms 696 KB Output is correct
15 Correct 3413 ms 700 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 39 ms 4432 KB Output is correct
18 Runtime error 245 ms 92356 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -