Submission #416579

#	Time	Username	Problem	Language	Result	Execution time	Memory
416579		wiwiho	Meetings (IOI18_meetings)	C++14	17 / 100	100 ms	12080 KiB

meetings

#include "meetings.h"

#include <bits/stdc++.h>

#define eb emplace_back
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}
#define mp make_pair
#define F first
#define S second
#define pob pop_back()
#define iter(a) a.begin(), a.end()

using namespace std;

typedef long long ll;

using pll = pair<ll, ll>;

struct Node{
    int v = 0, l = 0, r = 0, sz = 0;
};

vector<int> h;
vector<Node> st;

Node mergenode(Node ln, Node rn){
    int v = max({ln.v, rn.v, ln.r + rn.l});
    int l = ln.v == ln.sz ? ln.v + rn.l : ln.l;
    int r = rn.v == rn.sz ? rn.v + ln.r : rn.r;
    int sz = rn.sz + ln.sz;
    return Node({v, l, r, sz});
}

void build(int l, int r, int id){
    if(l == r){
        st[id].sz = r - l + 1;
        st[id].v = st[id].l = st[id].r = (h[l] == 1);
        return;
    }
    int m = (l + r) / 2;
    build(l, m, 2 * id + 1);
    build(m + 1, r, 2 * id + 2);
    st[id] = mergenode(st[2 * id + 1], st[2 * id + 2]);
}

Node query(int l, int r, int L, int R, int id){
    if(l == L && r == R){
        return st[id];
    }
    int M = (L + R) / 2;
    if(r <= M) return query(l, r, L, M, 2 * id + 1);
    else if(l > M) return query(l, r, M + 1, R, 2 * id + 2);
    else{
        return mergenode(query(l, M, L, M, 2 * id + 1), query(M + 1, r, M + 1, R, 2 * id + 2));
    }
}

vector<ll> minimum_costs(vector<int> H, vector<int> L,
                                     vector<int> R) {
    h = H;
    int m = L.size();
    int n = h.size();

    st.resize(4 * n);
    build(0, n - 1, 0);

    vector<ll> c(m);
    for(int i = 0; i < m; i++){
        int tmp = query(L[i], R[i], 0, n - 1, 0).v;
        //cerr << tmp << "\n";
        c[i] = tmp + (R[i] - L[i] + 1 - tmp) * 2;
    }
    
    return c;
}

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