Submission #1133903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133903		ncosiaafo	Meetings (IOI18_meetings)	C++20	100 / 100	2655 ms	594880 KiB

meetings

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

int const MAXN = 7.5e5+2;
ll const INF = 1e18;

struct Line {
    ll a, b;
    int o;
    Line() = default;
    Line(ll y) : a(0), b(y), o(0) {}
    Line(ll a, ll b) : a(a), b(b), o(0) {}
    Line(ll a, ll b, int o) : a(a), b(b), o(o) {}
    ll operator()(int x) const { return a*(x-o) + b; }
    bool operator==(Line const& lo) const {
        return a==lo.a && b==lo.b && o == lo.o;
    }
    bool operator!=(Line const& lo) const {
        return a!=lo.a || b!=lo.b || o != lo.o;
    }
};
Line const Mixed = Line(-1);

struct {
    int n;
    Line ln[4*MAXN];
    pair<ll, ll> meta[4*MAXN];
    ll lazy[4*MAXN];

    pair<ll, ll> GetMeta(int u, int L, int R) {
        if (ln[u] != Mixed) return make_pair(ln[u](L), ln[u](R));
        else return meta[u];
    }
    void Push(int u, int L, int R) { 
        if (!lazy[u]) return;
        if (lazy[u] < 0) lazy[u] = 0;
        if (ln[u] != Mixed) {
            ln[u].b += lazy[u];
            if (L != R) {
                lazy[u*2] = lazy[u*2+1] = -1;
                ln[u*2] = ln[u*2+1] = ln[u];
            }
        }
        else {
            meta[u].first += lazy[u];
            meta[u].second += lazy[u];
            if (L != R) {
                lazy[u*2] = (~lazy[u*2]?lazy[u*2]:0)+lazy[u];
                lazy[u*2+1] = (~lazy[u*2+1]?lazy[u*2+1]:0)+lazy[u];
            }
        }
        lazy[u] = 0;
    }
    void Pull(int u, int L, int R) {
        if (L == R) meta[u] = make_pair(ln[u](L), ln[u](R));
        else {
            if (ln[u*2] == ln[u*2+1]) ln[u] = ln[u*2];
            else ln[u] = Mixed;
            if (ln[u] == Mixed) {
                int M = (L+R)/2;
                meta[u] = make_pair(GetMeta(u*2, L, M).first, GetMeta(u*2+1, M+1, R).second);
            }
        }
    }
    void Setup(int _n) {
        n = _n;
        memset(lazy, 0, sizeof lazy);
        ln[1] = Line(INF);
        lazy[1] = -1;
    }
    void AddRange(int u, int L, int R, int i, int j, ll val) {
        Push(u, L, R);
        if (i > j) return;
        if (i <= L && R <= j) {
            lazy[u] = val;
            Push(u, L, R);
            return;
        }
        int M = (L+R)/2;
        AddRange(u*2, L, M, i, min(M,j), val);
        AddRange(u*2+1, M+1, R, max(i,M+1), j, val);
        Pull(u, L, R);
    }
    void AddRange(int l, int r, ll val) {
        AddRange(1, 0, n-1, l, r, val);
    }
    void AssignLine(int u, int L, int R, int i, int j, Line const& line) {
        Push(u, L, R);
        if (i > j) return;
        if (i <= L && R <= j) {
            ll LeftNew = line(L), RightNew = line(R);
            ll LeftOld, RightOld;
            tie(LeftOld, RightOld) = GetMeta(u, L, R);
            if (LeftNew <= LeftOld && RightNew <= RightOld) {
                ln[u] = line; lazy[u] = -1;
                Push(u, L, R);
                return;
            }
            else if (LeftNew > LeftOld && RightNew > RightOld) return;
        }
        int M = (L + R) / 2;
        AssignLine(u*2, L, M, i, min(M,j), line);
        AssignLine(u*2+1, M+1, R, max(M+1,i), j, line);
        Pull(u, L, R);
    }
    void AssignLine(int l, int r, ll a, ll b, int o) {
        Line _line(a,b,o);
        AssignLine(1, 0, n-1, l, r, _line);
    }
    ll GetVal(int u, int L, int R, int idx) {
        Push(u, L, R);
        if (L == R) return ln[u](L);
        if (ln[u] != Mixed) {
            return ln[u](idx);
        }
        int M = (L+R)/2;
        if (idx <= M) return GetVal(u*2, L, M, idx);
        else return GetVal(u*2+1, M+1, R, idx);
    }
    ll GetVal(int idx) {
        return GetVal(1, 0, n-1, idx);
    }
} LichaoL, LichaoR;

struct {
    int n;
    pair<int, int> Tbl[20][MAXN];

    void Setup(vector<int>& H) {
        n = H.size();
        for (int i = 0; i < n; ++i) {
            Tbl[0][i] = make_pair(H[i], i);
        }
        for (int b = 1; (1<<b) <= n; ++b) {
            for (int i = 0; i+(1<<b) <= n; ++i) {
                Tbl[b][i] = max(Tbl[b-1][i], Tbl[b-1][i+(1<<(b-1))]);
            }
        }
    }

    int GetMax(int l, int r) {
        int len = r-l+1;
        int lg2 = __builtin_clz(1) - __builtin_clz(len);
        int ii = max(Tbl[lg2][l], Tbl[lg2][r - (1<<lg2) +1]).second;
        return ii;
    }
} SparseTable;

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

    SparseTable.Setup(H);
    LichaoL.Setup(n);
    LichaoR.Setup(n);

    vector<ll> AnsL(q, 0);
    vector<ll> AnsR(q, 0);

    vector<vector<int>> OfflineL(n);
    vector<vector<int>> OfflineR(n);
    
    for (int i = 0; i < q; ++i) {
        int rt = SparseTable.GetMax(L[i], R[i]);
        AnsR[i] = (ll)(rt+1-L[i]) * H[rt];
        AnsL[i] = (ll)(R[i]+1-rt) * H[rt];
        if (rt < R[i]) {
            int rtR = SparseTable.GetMax(rt+1, R[i]);
            OfflineR[rtR].emplace_back(i);
        }
        if (rt > L[i]) {
            int rtL = SparseTable.GetMax(L[i], rt-1);
            OfflineL[rtL].emplace_back(i);
        }
    }

    function<void(int,int)> Cartesian;
    Cartesian = [&](int l, int r) {
        int rt = SparseTable.GetMax(l, r);
        if (rt > l) Cartesian(l, rt-1);
        if (rt < r) Cartesian(rt+1, r);
        
        ll OptR = ((rt > l) ? LichaoR.GetVal(rt-1) : 0LL) + H[rt];
        LichaoR.AssignLine(rt, rt, 0, OptR, 0);
        if (rt < r) {
            LichaoR.AddRange(rt+1, r, (ll)(rt-l+1) * H[rt]);
            if (l < rt) { 
                LichaoR.AssignLine(rt+1, r, H[rt], OptR, rt);
            }
        }
        for (int qi: OfflineR[rt]) {
            AnsR[qi] += LichaoR.GetVal(R[qi]);
        }

        ll OptL = ((rt < r) ? LichaoL.GetVal(rt+1) : 0LL) + H[rt];
        LichaoL.AssignLine(rt, rt, 0, OptL, 0);
        if (rt > l) {
            LichaoL.AddRange(l, rt-1, (ll)(r+1-rt) * H[rt]);
            if (r > rt) {
                LichaoL.AssignLine(l, rt-1, -H[rt], OptL + (ll)(rt-l)*H[rt], l);
            }
        }
        for (int qi: OfflineL[rt]) {
            AnsL[qi] += LichaoL.GetVal(L[qi]);
        }
    };
    Cartesian(0, n-1);


    for (int i = 0; i < q; ++i) AnsL[i] = min(AnsL[i], AnsR[i]);
    return AnsL;
}

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