Submission #106741

#	Time	Username	Problem	Language	Result	Execution time	Memory
106741		ppnxblstr	Meetings (IOI18_meetings)	C++14	36 / 100	698 ms	196512 KiB

meetings

#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 (stderr)

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