oj.uz

Submission #106741

# Submission time Handle Problem Language Result Execution time Memory
106741 2019-04-19T22:54:19 Z ppnxblstr Meetings (IOI18_meetings) C++14
36 / 100
 698 ms 196512 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

const int MXN = 100005;
int segT[4*MXN];
int lb[4*MXN];
int rb[4*MXN];
int pre[MXN];
int nxt[MXN];
vector<int> occurs;
void build(int c, int l, int r){
    lb[c] = l;
    rb[c] = r;
    if(l == r){
        segT[c] = pre[l] - nxt[l];
        return;
    }
    int k = (l + r)/2;
    build(2*c,l,k);
    build(2*c+1,k+1,r);
    segT[c] = min(segT[2*c], segT[2*c+1]);
}
int query(int c, int l, int r){
    if(lb[c] == l && rb[c] == r) return segT[c];
    int k = (lb[c] + rb[c])/2;
    if(l <= k && k < r) return min(query(2*c,l,k), query(2*c+1,k+1,r));
    else if(r <= k) return query(2*c,l,r);
    else return query(2*c+1,l,r);
}
long long costs[5005][5005];
vector<long long> minimum_costs(vector<int> H, vector<int> L,
                                     vector<int> R) {
    int Q = L.size();
    vector<long long> C(Q);
    int N = H.size();
    if(N <= 5000){
        // Sol 1: Preprocess the N^2 possibilities and then loop for selection.
        for(int i = 0; i < N; i++){
            // Starting at i.
            int cur = H[i];
            costs[i][i] = 0ll;
            for(int j = i-1; j >= 0; j--){
                cur = max(cur, H[j]);
                costs[i][j] = costs[i][j+1] + (long long)cur;
            }
            cur = H[i];
            for(int j = i+1; j < N; j++){
                cur = max(cur, H[j]);
                costs[i][j] = costs[i][j-1] + (long long)cur;
            }
        }
        for(int i = 0; i < Q; i++){
            C[i] = 1e18;
            for(int j = L[i]; j <= R[i]; j++){
                C[i] = min(C[i],costs[j][L[i]] + costs[j][R[i]] + (long long)H[j]);
            }
        }
    }else{
        // Sol 2: Use segment tree to answer RMQ of a derived parameter 'prev - next + 3 + 2R - 2L'.
        for(int i = 0; i < N; i++){
            if(H[i] == 2) occurs.push_back(i);
        }
        for(int i = 0; i < N; i++){
            if(H[i] == 2){
                pre[i] = nxt[i] = i;
                continue;
            }
            if(i > occurs.front())
                pre[i] = *(lower_bound(occurs.begin(), occurs.end(), i)-1);
            if(i < occurs.back())
                nxt[i] = *upper_bound(occurs.begin(), occurs.end(), i);
        }
        build(1,0,N-1);
        for(int i = 0; i < Q; i++){
            int idx = lower_bound(occurs.begin(), occurs.end(), L[i]) - occurs.begin();
            if(idx == occurs.size() || occurs[idx] > R[i]){
                // Not found any 2's in there
                C[i] = R[i] - L[i] + 1;
            }else{
                // 3 Cases: f, mid, s
                int lidx = upper_bound(occurs.begin(), occurs.end(), R[i]) - 1 - occurs.begin();
                // Case f
                int a1 = 2*R[i] - occurs[idx] - L[i] + 2;
                // Case mid
                int a2 = query(1,occurs[idx],occurs[lidx]) + 3 + 2*R[i] - 2*L[i];
                // Case s
                int a3 = occurs[lidx] - 2*L[i] + 2 + R[i];
                C[i] = min(a1,min(a2,a3));
            }
        }
    }
    return C;
}

Compilation message

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:77:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(idx == occurs.size() || occurs[idx] > R[i]){
                ~~~~^~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 82 ms 82892 KB Output is correct
3 Correct 83 ms 82832 KB Output is correct
4 Correct 83 ms 82908 KB Output is correct
5 Correct 82 ms 82884 KB Output is correct
6 Correct 81 ms 82800 KB Output is correct
7 Correct 84 ms 82876 KB Output is correct
8 Correct 81 ms 82908 KB Output is correct
9 Correct 82 ms 82864 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 82 ms 82892 KB Output is correct
3 Correct 83 ms 82832 KB Output is correct
4 Correct 83 ms 82908 KB Output is correct
5 Correct 82 ms 82884 KB Output is correct
6 Correct 81 ms 82800 KB Output is correct
7 Correct 84 ms 82876 KB Output is correct
8 Correct 81 ms 82908 KB Output is correct
9 Correct 82 ms 82864 KB Output is correct
10 Correct 482 ms 196416 KB Output is correct
11 Correct 698 ms 196360 KB Output is correct
12 Correct 481 ms 196476 KB Output is correct
13 Correct 690 ms 196424 KB Output is correct
14 Correct 496 ms 196512 KB Output is correct
15 Correct 481 ms 196412 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 51 ms 1884 KB Output is correct
3 Correct 166 ms 7640 KB Output is correct
4 Correct 125 ms 7300 KB Output is correct
5 Correct 119 ms 7700 KB Output is correct
6 Correct 126 ms 7692 KB Output is correct
7 Correct 121 ms 7680 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 51 ms 1884 KB Output is correct
3 Correct 166 ms 7640 KB Output is correct
4 Correct 125 ms 7300 KB Output is correct
5 Correct 119 ms 7700 KB Output is correct
6 Correct 126 ms 7692 KB Output is correct
7 Correct 121 ms 7680 KB Output is correct
8 Incorrect 160 ms 7388 KB Output isn't correct
9 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 82 ms 82892 KB Output is correct
3 Correct 83 ms 82832 KB Output is correct
4 Correct 83 ms 82908 KB Output is correct
5 Correct 82 ms 82884 KB Output is correct
6 Correct 81 ms 82800 KB Output is correct
7 Correct 84 ms 82876 KB Output is correct
8 Correct 81 ms 82908 KB Output is correct
9 Correct 82 ms 82864 KB Output is correct
10 Correct 482 ms 196416 KB Output is correct
11 Correct 698 ms 196360 KB Output is correct
12 Correct 481 ms 196476 KB Output is correct
13 Correct 690 ms 196424 KB Output is correct
14 Correct 496 ms 196512 KB Output is correct
15 Correct 481 ms 196412 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 51 ms 1884 KB Output is correct
18 Correct 166 ms 7640 KB Output is correct
19 Correct 125 ms 7300 KB Output is correct
20 Correct 119 ms 7700 KB Output is correct
21 Correct 126 ms 7692 KB Output is correct
22 Correct 121 ms 7680 KB Output is correct
23 Incorrect 160 ms 7388 KB Output isn't correct
24 Halted 0 ms 0 KB -