제출 #286454

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
286454		dolphingarlic	모임들 (IOI18_meetings)	C++14	36 / 100	1060 ms	11000 KiB

meetings

#include "meetings.h"

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

struct Node {
    int l, r, a, b, tot;

    Node operator+(Node B) {
        Node ret = {l, B.r, (tot == r - l + 1 ? tot + B.a : a),
                    (B.tot == B.r - B.l + 1 ? b + B.tot : B.b),
                    max({tot, B.tot, b + B.a})};
        return ret;
    }
} segtree[400001];

int n, h[100001];
ll dp[5000];

void build(int node = 1, int l = 0, int r = n - 1) {
    if (l == r) segtree[node] = {l, r, h[l] == 1, h[l] == 1, h[l] == 1};
    else {
        int mid = (l + r) / 2;
        build(node * 2, l, mid);
        build(node * 2 + 1, mid + 1, r);
        segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];
    }
}

Node query(int a, int b, int node = 1, int l = 0, int r = n - 1) {
    if (a <= l && b >= r) return segtree[node];
    int mid = (l + r) / 2;
    if (mid >= a) {
        if (mid + 1 <= b) return query(a, b, node * 2, l, mid) + query(a, b, node * 2 + 1, mid + 1, r);
        return query(a, b, node * 2, l, mid);
    }
    return query(a, b, node * 2 + 1, mid + 1, r);
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    n = H.size();
    for (int i = 0; i < n; i++) h[i] = H[i];
    int Q = int(L.size());
    vector<long long> C(Q);

    if (Q <= 5000) {
        for (int i = 0; i < Q; i++) {
            memset(dp, 0, sizeof dp);
            stack<pair<int, ll>> stck;
            ll val = 0;
            for (int j = L[i]; j <= R[i]; j++) {
                while (stck.size() && H[stck.top().first] <= H[j]) {
                    val -= H[stck.top().first] * stck.top().second;
                    stck.pop();
                }
                ll rng = (stck.size() ? j - stck.top().first : j - L[i] + 1);
                val += rng * H[j];
                dp[j] += val;
                stck.push({j, rng});
                // cout << dp[j] << ' ';
            }
            // cout << "| ";
            while (stck.size()) stck.pop();
            val = 0;
            for (int j = R[i]; j >= L[i]; j--) {
                while (stck.size() && H[stck.top().first] <= H[j]) {
                    val -= H[stck.top().first] * stck.top().second;
                    stck.pop();
                }
                ll rng = (stck.size() ? stck.top().first - j : R[i] - j + 1);
                val += rng * H[j];
                dp[j] += val - H[j];
                stck.push({j, rng});
                // cout << dp[j] << ' ';
            }
            // cout << '\n';
            C[i] = *min_element(dp + L[i], dp + R[i] + 1);
        }
    } else {
        build();
        for (int i = 0; i < Q; i++) {
            C[i] = 2 * (R[i] - L[i] + 1) - query(L[i], R[i]).tot;
        }
    }
    return C;
}

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