Submission #702177

#	Time	Username	Problem	Language	Result	Execution time	Memory
702177		qwerasdfzxcl	Meetings (IOI18_meetings)	C++17	60 / 100	2433 ms	297232 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

constexpr int MAXN = 100100;
constexpr int MAXH = 20;
constexpr ll INF = 4e18;

int n, h, q;
int a[MAXN], l[MAXN], r[MAXN];
ll C[MAXN];

struct Seg{
    ll tree[MAXN*4], lazy[MAXN*4];

    void init(int i, int l, int r){
        lazy[i] = 0;
        if (l==r) {tree[i] = C[l]; return;}

        int m = (l+r)>>1;
        init(i<<1, l, m); init(i<<1|1, m+1, r);
        tree[i] = min(tree[i<<1], tree[i<<1|1]);
    }
    void propagate(int i, int l, int r){
        if (!lazy[i]) return;
        tree[i] += lazy[i];
        if (l!=r){
            lazy[i<<1] += lazy[i];
            lazy[i<<1|1] += lazy[i];
        }
        lazy[i] = 0;
    }
    void update(int i, int l, int r, int s, int e, ll x){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i] += x;
            propagate(i, l, r);
            return;
        }

        int m = (l+r)>>1;
        update(i<<1, l, m, s, e, x); update(i<<1|1, m+1, r, s, e, x);
        tree[i] = min(tree[i<<1], tree[i<<1|1]);
    }
    ll query(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if (r<s || e<l) return INF;
        if (s<=l && r<=e) return tree[i];

        int m = (l+r)>>1;
        return min(query(i<<1, l, m, s, e), query(i<<1|1, m+1, r, s, e));
    }
}tree;

struct Foo{
    int L[MAXN], R[MAXN];

    void init(int k){
        int prv = 0;
        for (int i=1;i<=n;i++) if (a[i]>=k){
            L[i] = R[i] = 0;
            C[i] += n;
            for (int j=prv+1;j<i;j++){
                L[j] = prv+1, R[j] = i-1;
                C[j] += n - (i-prv-1);
            }

            prv = i;
        }

        for (int j=prv+1;j<n+1;j++){
            L[j] = prv+1, R[j] = n;
            C[j] += n - (n+1-prv-1);
        }
    }

    void query(int l, int r, int typ){
        if (L[l]){
            tree.update(1, 1, n, l, min(r, R[l]), (l-L[l]) * typ);
        }
        if (R[r]){
            tree.update(1, 1, n, max(l, L[r]), r, (R[r]-r) * typ);
        }
    }

}F[MAXH+1];

int mx[5050][5050];
ll dp[5050][5050];
vector<ll> naive(){
    for (int i=1;i<=n;i++){
        mx[i][i] = a[i];
        dp[i][i] = a[i];
        for (int j=i+1;j<=n;j++){
            mx[i][j] = max(mx[i][j-1], a[j]);
            dp[i][j] = dp[i][j-1] + mx[i][j];
        }
        for (int j=i-1;j>0;j--){
            mx[i][j] = max(mx[i][j+1], a[j]);
            dp[i][j] = dp[i][j+1] + mx[i][j];
        }
    }

    vector<ll> ans;
    for (int i=1;i<=q;i++){
        ll rans = INF;
        for (int j=l[i];j<=r[i];j++){
            rans = min(rans, dp[j][l[i]] + dp[j][r[i]] - a[j]);
        }
        ans.push_back(rans);
    }

    return ans;
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
    n = H.size();
    q = L.size();
    h = *max_element(H.begin(), H.end());

    for (int i=1;i<=n;i++){
        a[i] = H[i-1];
    }
    for (int i=1;i<=q;i++){
        l[i] = L[i-1] + 1;
        r[i] = R[i-1] + 1;
    }

    if (n <= 5000 && q <= 5000) return naive();
    for (int i=1;i<=h;i++) F[i].init(i);

    vector<ll> ans;
    tree.init(1, 1, n);

    for (int i=1;i<=q;i++){
        for (int j=1;j<=h;j++) F[j].query(l[i], r[i], 1);
        ans.push_back(tree.query(1, 1, n, l[i], r[i]) - (ll)h * (n-(r[i]-l[i]+1)));
        for (int j=1;j<=h;j++) F[j].query(l[i], r[i], -1);
    }

    return ans;
}

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