Submission #713884

#	Time	Username	Problem	Language	Result	Execution time	Memory
713884		PixelCat	Meetings (IOI18_meetings)	C++14	0 / 100	11 ms	2140 KiB

meetings

#ifdef NYAOWO
#include "grader.cpp"
#endif
#include "meetings.h"

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
using namespace std;
using LL = long long;
using pii = pair<LL, LL>;

const int MAXN = 5010;
const LL INF = 1e10;

int N, Q;
LL h[MAXN];
LL cnt[MAXN][20];
LL cl[MAXN], cr[MAXN];

LL query(int l, int r) {
    LL tot = 0;
    vector<pii> v;  // {index, value}
    v.eb(l - 1, INF);
    For(i, l, r) {
        while(v.back().S < h[i]) {
            auto p = v.back(); v.pop_back();
            tot -= p.S * (p.F - v.back().F);
        }
        tot += h[i] * (i - v.back().F);
        cl[i] = tot;
        v.eb(i, h[i]);
    }

    tot = 0;
    v.clear();
    v.eb(r + 1, INF);
    Forr(i, r, l) {
        while(v.back().S < h[i]) {
            auto p = v.back(); v.pop_back();
            tot -= p.S * (v.back().F - p.F);
        }
        tot += h[i] * (v.back().F - i);
        cr[i] = tot;
        v.eb(i, h[i]);
    }

    LL ans = cl[l] + cr[l] - h[l];
    For(i, l + 1, r) ans = min(ans, cl[i] + cr[i] - h[i]);
    return ans;
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
    N = sz(H);
    Q = sz(L);
    For(i, 0, N - 1) h[i] = H[i];
    // if(N <= 5000) {
    //     vector<LL> C(Q);
    //     For(i, 0, Q - 1) {
    //         C[i] = query(L[i], R[i]);
    //     }
    //     return C;
    // }

    vector<LL> le, ri;
    le.eb(-1); ri.eb(-1);
    int now = 0;
    For(i, 0, N - 1) {
        if(h[i] == 2) now = 0;
        else now++;
        cnt[i][0] = now;
        // cout << i << " " << h[i] << " " << now << "\n";
        if(h[i] == 1) {
            if(i == 0 || h[i - 1] != 1) le.eb(i);
            if(i == N - 1 || h[i + 1] != 1) ri.eb(i);
        }
    }
    le.eb(N); ri.eb(N);
    For(j, 1, 19) For(i, 0, N - 1) {
        cnt[i][j] = cnt[i][j - 1];
        if(i + (1 << (j - 1)) < N) cnt[i][j] = max(cnt[i][j], cnt[i + (1 << (j - 1))][j - 1]);
    }
    auto get_max = [&](int a, int b) {
        int k = __lg(b - a + 1);
        return max(cnt[a][k], cnt[b - (1 << k) + 1][k]);
    };
    // for(auto &i:le) cout << i << " "; cout << endl;
    // for(auto &i:ri) cout << i << " "; cout << endl;
    vector<LL> C;
    For(i, 0, Q - 1) {
        LL a = L[i];
        LL b = R[i];
        LL ll = *lower_bound(all(le), a);
        LL lr = lower_bound(all(ri), a) - ri.begin();
        LL rl = prev(upper_bound(all(le), b)) - le.begin();
        LL rr = *prev(upper_bound(all(ri), b));
        // cout << ll << " " << lr << " " << rl << " " << rr << "\n" << flush;
        if(le[lr] > b || ri[rl] < a) {
            C.eb(2ll * (b - a + 1));
            continue;
        }
        LL mx = 0;
        if(ll <= rr) {
            mx = max(mx, get_max(ll, rr));
        }
        if(ri[lr] >= a && le[lr] <= a) {
            mx = max(mx, ri[lr] - a + 1);
        }
        if(le[rl] <= b && ri[rl] >= b) {
            mx = max(mx, b - le[rl] + 1);
        }
        mx = min(mx, b - a + 1);
        C.eb(2ll * (b - a + 1) - mx);
    }
    return C;
}

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