Submission #115529

#	Time	Username	Problem	Language	Result	Execution time	Memory
115529		onjo0127	Meetings (IOI18_meetings)	C++11	36 / 100	763 ms	294652 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

struct segtree {
    vector<int> T;
    segtree(int sz) { T.resize(4*sz); }
    void init(vector<int>& A, int idx, int s, int e) {
        if(s == e) {
            T[idx] = A[s-1];
            return;
        }
        int m = s+e >> 1;
        init(A, idx*2, s, m);
        init(A, idx*2+1, m+1, e);
        T[idx] = max(T[idx*2], T[idx*2+1]);
    }
    int get(int idx, int s, int e, int l, int r) {
        if(r < s || e < l) return -1e9;
        if(l <= s && e <= r) return T[idx];
        int m = s+e >> 1;
        return max(get(idx*2, s, m, l, r), get(idx*2+1, m+1, e, l, r));
    }
};

int MH[5009][5009], Lg[100009], Rg[100009];
long long PS[5009][5009];

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    int Q = L.size(), N = H.size();
    vector<long long> C(Q);
    if(Q <= 5000 && N <= 5000) {
        for(int i=0; i<N; i++) {
            for(int j=i, mx=H[i]; j>=0; j--) mx = max(mx, H[j]), MH[i][j] = mx;
            for(int j=i, mx=H[i]; j<N; j++) mx = max(mx, H[j]), MH[i][j] = mx;
            PS[i][0] = MH[i][0];
            for(int j=1; j<N; j++) PS[i][j] = PS[i][j-1] + MH[i][j];
        }
        for(int i=0; i<Q; i++) {
            long long ans = 1LL * 1e18;
            for(int j=L[i]; j<=R[i]; j++) {
                long long x = PS[j][R[i]] - (L[i] ? PS[j][L[i]-1] : 0);
                ans = min(ans, x);
            }
            C[i] = ans;
        }
        return C;
    }
    vector<int> A(N);
    for(int i=0, s=0; i<N; i++) {
        if(H[i] == 1) ++s;
        else s = 0;
        A[i] = s;
    }
    int l = -1;
    for(int i=0; i<N; i++) {
        if(H[i] == 2) l = i;
        Lg[i] = l;
    }
    int r = N;
    for(int i=N-1; i>=0; i--) {
        if(H[i] == 2) r = i;
        Rg[i] = r;
    }
    segtree seg(N+1);
    seg.init(A, 1, 1, N);
    for(int i=0; i<Q; i++) {
        int mx = 0, ans = 2 * (R[i] - L[i] + 1);
        if(H[L[i]] == 1 && Rg[L[i]] > R[i]) {C[i] = R[i] - L[i] + 1; continue;}
        if(H[L[i]] == 1) mx = max(mx, Rg[L[i]] - L[i]), L[i] = Rg[L[i]];
        if(H[R[i]] == 1) mx = max(mx, R[i] - Lg[R[i]]), R[i] = Lg[R[i]];
        mx = max(mx, seg.get(1, 1, N, L[i]+1, R[i]+1));
        C[i] = ans - mx;
    }
    return C;
}

Compilation message (stderr)

meetings.cpp: In member function 'void segtree::init(std::vector<int>&, int, int, int)':
meetings.cpp:13:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = s+e >> 1;
                 ~^~
meetings.cpp: In member function 'int segtree::get(int, int, int, int, int)':
meetings.cpp:21:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = s+e >> 1;
                 ~^~

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40