Submission #1227691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227691		Hamed_Ghaffari	Meetings (IOI18_meetings)	C++20	100 / 100	2641 ms	276640 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
#define mins(a, b) (a = min(a, b))

const int MXN = 750005;

int n;

inline int rev(int i) { return n-1-i; }

struct node {
    ll gl, lz_add, lz_set;
    bool flag_set;
    node(): gl(0), lz_add(0), lz_set(0), flag_set(0) {}
};

inline void apply_set(node &v, ll x, int l) {
    v.gl = x*l;
    v.lz_add = 0;
    v.lz_set = x;
    v.flag_set = 1;
}

inline void apply_add(node &v, ll x) {
    v.gl += x;
    v.lz_add += x;
}

struct DS {
    node seg[MXN<<2];
    inline void push(int l, int r, int id) {
        if(seg[id].flag_set) {
            apply_set(seg[lc], seg[id].lz_set, l);
            apply_set(seg[rc], seg[id].lz_set, mid);
            seg[id].flag_set = 0;
        }
        if(seg[id].lz_add) {
            apply_add(seg[lc], seg[id].lz_add);
            apply_add(seg[rc], seg[id].lz_add);
            seg[id].lz_add = 0;
        }
    }
    void upd_set(int s, int e, ll x, int l=0, int r=n, int id=1) {
        if(s>=r || l>=e) return;
        if(s<=l && r<=e) {
            apply_set(seg[id], x, l);
            return;
        }
        push(l, r, id);
        upd_set(s, e, x, l, mid, lc);
        upd_set(s, e, x, mid, r, rc);
        seg[id].gl = seg[lc].gl;
    }
    void upd_add(int s, int e, ll x, int l=0, int r=n, int id=1) {
        if(s>=r || l>=e) return;
        if(s<=l && r<=e) {
            apply_add(seg[id], x);
            return;
        }
        push(l, r, id);
        upd_add(s, e, x, l, mid, lc);
        upd_add(s, e, x, mid, r, rc);
        seg[id].gl = seg[lc].gl;
    }
    ll get(int p, int l=0, int r=n, int id=1) {
        if(r-l == 1) return seg[id].gl;
        push(l, r, id);
        return p<mid ? get(p, l, mid, lc) : get(p, mid, r, rc);
    }
    int res;
    void find_(int s, int e, ll A, ll B, ll C, int l=0, int r=n, int id=1) {
        if(s>=r || l>=e || res!=s-1) return;
        if(s<=l && r<=e) {
            if(seg[id].gl+C<A+B*l) return;
            if(r-l==1) {
                res = l;
                return;
            }
            push(l, r, id);
            if(seg[rc].gl+C>=A+B*mid) find_(s, e, A, B, C, mid, r, rc);
            else find_(s, e, A, B, C, l, mid, lc);
            return;
        }
        push(l, r, id);
        find_(s, e, A, B, C, mid, r, rc);
        find_(s, e, A, B, C, l, mid, lc);
    }
    int find(int s, int e, ll A, ll B, ll C) {
        res = s-1;
        find_(s, e, A, B, C);
        return res;
    }
} pre, suf;

pii seg[MXN<<2];
void build(vector<int> &H, int l=0, int r=n, int id=1) {
    if(r-l == 1) {
        seg[id] = pii(H[l], l);
        return;
    }
    build(H, l, mid, lc);
    build(H, mid, r, rc);
    seg[id] = max(seg[lc], seg[rc]);
}
pii get_max(int s, int e, int l=0, int r=n, int id=1) {
    if(s>=r || l>=e) return pii(0, 0);
    if(s<=l && r<=e) return seg[id];
    return max(get_max(s, e, l, mid, lc), get_max(s, e, mid, r, rc));
}

int L[MXN], R[MXN], ord[MXN];
vector<ll> ans;
vector<int> Q[MXN];

vector<ll> minimum_costs(vector<int> H, vector<int> ql, vector<int> qr) {
    n = H.size();
    for(int i=0; i<n; i++)
        for(L[i]=i-1; L[i]>=0 && pii(H[L[i]], L[i])<pii(H[i], i); L[i]=L[L[i]]);
    for(int i=n-1; i>=0; i--)
        for(R[i]=i+1; R[i]<n && pii(H[R[i]], R[i])<pii(H[i], i); R[i]=R[R[i]]);
    build(H);
    for(int i=0; i<ql.size(); i++)
        Q[get_max(ql[i], qr[i]+1).second].push_back(i);
    ans = vector<ll>(ql.size(), 1e18);
    iota(ord, ord+n, 0);
    sort(ord, ord+n, [&](int i, int j) {
        return pii(H[i], i) < pii(H[j], j);
    });
    for(int _=0,i; _<n; _++) {
        i = ord[_];
        for(int j : Q[i]) {
            mins(ans[j], 1ll*(qr[j]-ql[j]+1)*H[i]);
            mins(ans[j], pre.get(qr[j]) + 1ll*(i-ql[j]+1)*H[i]);
            mins(ans[j], suf.get(rev(ql[j])) + 1ll*(qr[j]-i+1)*H[i]);
        }

        pre.upd_add(i, i+1, L[i]==i-1 ? H[i] : pre.get(i-1)+H[i]);
        if(R[i]>i+1) {
            ll A = pre.get(i)-1ll*i*H[i];
            int wh = pre.find(i+1, R[i], A, H[i], 1ll*(i-L[i])*H[i]);
            pre.upd_set(i+1, wh+1, H[i]);
            pre.upd_add(i+1, wh+1, A);
            pre.upd_add(wh+1, R[i], 1ll*(i-L[i])*H[i]);
        }

        suf.upd_add(rev(i), rev(i)+1, R[i]==i+1 ? H[i] : suf.get(rev(i+1))+H[i]);
        if(L[i]<i-1) {
            ll A = suf.get(rev(i))-1ll*rev(i)*H[i];
            int wh = suf.find(rev(i-1), rev(L[i]), A, H[i], 1ll*(R[i]-i)*H[i]);
            suf.upd_set(rev(i-1), wh+1, H[i]);
            suf.upd_add(rev(i-1), wh+1, A);
            suf.upd_add(wh+1, rev(L[i]), 1ll*(R[i]-i)*H[i]);
        }
    }
    return ans;
}

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