oj.uz

답안 #106737

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106737 2019-04-19T22:37:44 Z ppnxblstr 모임들 (IOI18_meetings) C++14
19 / 100
 693 ms 196472 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);
}
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,idx,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:76: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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 80 ms 82912 KB Output is correct
3 Correct 81 ms 82840 KB Output is correct
4 Correct 81 ms 82924 KB Output is correct
5 Correct 81 ms 82816 KB Output is correct
6 Correct 82 ms 82832 KB Output is correct
7 Correct 80 ms 82840 KB Output is correct
8 Correct 81 ms 82820 KB Output is correct
9 Correct 81 ms 82908 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 80 ms 82912 KB Output is correct
3 Correct 81 ms 82840 KB Output is correct
4 Correct 81 ms 82924 KB Output is correct
5 Correct 81 ms 82816 KB Output is correct
6 Correct 82 ms 82832 KB Output is correct
7 Correct 80 ms 82840 KB Output is correct
8 Correct 81 ms 82820 KB Output is correct
9 Correct 81 ms 82908 KB Output is correct
10 Correct 482 ms 196424 KB Output is correct
11 Correct 693 ms 196384 KB Output is correct
12 Correct 476 ms 196392 KB Output is correct
13 Correct 676 ms 196472 KB Output is correct
14 Correct 479 ms 196428 KB Output is correct
15 Correct 490 ms 196396 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 46 ms 1900 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 46 ms 1900 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 80 ms 82912 KB Output is correct
3 Correct 81 ms 82840 KB Output is correct
4 Correct 81 ms 82924 KB Output is correct
5 Correct 81 ms 82816 KB Output is correct
6 Correct 82 ms 82832 KB Output is correct
7 Correct 80 ms 82840 KB Output is correct
8 Correct 81 ms 82820 KB Output is correct
9 Correct 81 ms 82908 KB Output is correct
10 Correct 482 ms 196424 KB Output is correct
11 Correct 693 ms 196384 KB Output is correct
12 Correct 476 ms 196392 KB Output is correct
13 Correct 676 ms 196472 KB Output is correct
14 Correct 479 ms 196428 KB Output is correct
15 Correct 490 ms 196396 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Incorrect 46 ms 1900 KB Output isn't correct
18 Halted 0 ms 0 KB -