oj.uz

Submission #92313

# Submission time Handle Problem Language Result Execution time Memory
92313 2019-01-02T13:15:35 Z Retro3014 Meetings (IOI18_meetings) C++17
0 / 100
 791 ms 1628 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;
}


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(i, maxi(min(i, j), max(i, j)));
            }
            for(int j=0; j<Q; j++){
                C[j]=min(C[j], sum(L[j], R[j]));
            }
        }
    }else{
        
    }
    return C;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Incorrect 23 ms 1628 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 348 KB Output is correct
2 Incorrect 23 ms 1628 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 Incorrect 791 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -