Submission #417095

#	Time	Username	Problem	Language	Result	Execution time	Memory
417095		balbit	Meetings (IOI18_meetings)	C++14	41 / 100	327 ms	14052 KiB

meetings

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

#define ll long long
#define int ll
#define pii pair<int, int>
#define pb push_back
#define f first
#define s second

#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
#define MX(a,b) a = max(a,b)


#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<"- "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)

#endif // BALBIT

const int maxn = 1e5+5;

vector<int> pos[21];

struct zsk{
    ll s[maxn*2];

    ll QU(int l, int r) {
        // range max query
        ll re = 0;
        for (l += maxn, r += maxn; l<r; l>>=1, r>>=1) {
            if (l&1) re = max(re, s[l++]);
            if (r&1) re = max(re, s[--r]);
        }
        return re;
    }

    void MO(int p, ll v) {
        p += maxn;
        for (s[p] = v; p>1; p>>=1) {
            s[p>>1] = max(s[p], s[p^1]);
        }
    }
    void clr(){
        memset(s, 0, sizeof s);
    }
    zsk(){
//        clr();
    }
};

ll L[maxn], R[maxn], H[maxn];
int n;
ll lval[maxn], rval[maxn];

zsk hseg;
zsk vseg;

ll getleft(int i, int lp) {
    int bg = hseg.QU(lp, i-1+1);
    if (bg == 0) return 0;
//    assert(bg < H[i]);
    int hi = *lower_bound(ALL(pos[bg]), lp); // last one in the range
    if (L[hi] >= lp) {
        return vseg.QU(lp, i) + (i-lp) * (ll)(H[i] - bg);
    }
    ll ret = vseg.QU(hi+1, i);
    MX(ret, max(getleft(hi, lp), rval[hi]));
    return ret + (i-lp) * (ll)(H[i] - bg);
}

ll getright(int i, int rp) {
    int bg = hseg.QU(i+1, rp+1);
    if (bg == 0) return 0;
    int hi = *prev(upper_bound(ALL(pos[bg]), rp)); // last one in the range
    if (R[hi] <= rp) {
        return vseg.QU(i+1, rp+1) + (rp-i) * (ll)(H[i] - bg);
    }
    ll ret = vseg.QU(i+1, hi);
    MX(ret, max(getright(hi, rp), lval[hi]));
    return ret + (rp-i) * (ll)(H[i] - bg);
}

//std::vector<long long> mc2(std::vector<signed> H, std::vector<signed> QL,
//                                     std::vector<signed> QR){
//    vector<ll> re;
//    REP(q, SZ(QL)) {
//        int l = QL[q], r = QR[q];
//        ll rt = -1;
//        for (int c = l; c<=r; ++c) {
//            ll rr = 0;
//            ll mx = 0;
//            for (int j = c; j>=l; --j) {
//                MX(mx, (ll)H[j]); rr += mx;
//            }
//            mx = H[c];
//            for (int j = c+1; j<=r; ++j) {
//                MX(mx, (ll)H[j]); rr += mx;
//            }
//            if (rt == -1 || rr < rt) rt = rr;
//        }
//        re.pb(rt);
//    }
//    return re;
//}

std::vector<long long> minimum_costs(std::vector<signed> _H, std::vector<signed> QL,
                                     std::vector<signed> QR) {
    vseg.clr();
    hseg.clr();
    REP1(i,20) pos[i].clear();
    memset(lval,0, sizeof lval);
    memset(rval,0, sizeof rval);

    n = SZ(_H);
    H[0] = H[n+1] = 1000000001;
    vector<int> hei;
    hei.pb(0);
    REP1(i,n) {
        H[i] = _H[i-1];
        pos[H[i]].pb(i);
        while (H[hei.back()] < H[i]) {
            hei.pop_back();
        }
        L[i] = hei.back()+1;
        hei.pb(i);
    }
    REP(i, n+2) hseg.MO(i,H[i]);
    hei.clear(); hei.pb(n+1);
    for (int i = n; i>=1; --i) {
        while (H[hei.back()] < H[i]) {
            hei.pop_back();
        }
        R[i] = hei.back()-1;
        hei.pb(i);
    }
    REP1(i,n) {
        bug(i, L[i], R[i]);
    }
    for (int th = 1; th<=20; ++th) {
        // town hall? no. target height :D
        REP1(i,n) {
            if (H[i] == th) {
                lval[i] = getleft(i, L[i]);
                rval[i] = getright(i, R[i]);
                bug(i, lval[i], rval[i]);
                vseg.MO(i, max(lval[i], rval[i]));
            }
        }
    }

    vector<ll> ans(SZ(QL));

    REP(tat, SZ(QL)) {
        int ql = QL[tat], qr = QR[tat];
        ++ql; ++qr;
        int bg = hseg.QU(ql, qr+1);
        bug(bg);
        int a = *lower_bound(ALL(pos[bg]), ql);
        int b = *prev(upper_bound(ALL(pos[bg]), qr));
//        assert(ql >= L[a]);
//        assert(qr <= R[b]);
        bug(bg, a,b);
        ll ret = vseg.QU(a+1, b);

        MX(ret, getleft(a, ql));
        MX(ret, getright(b, qr));
        if (a!=b) {
            MX(ret, rval[a]);
            MX(ret, lval[b]);
        }
        bug(ret);
        ans[tat] = (qr-ql+1) * bg - ret;
    }

    return ans;

}

//signed main(){
//    int n; cin>>n;
//    REP(i,1000) {
//        vector<signed> h;
//        REP(i,n) h.pb(rand()%5+1);
//        vector<signed> a,b;
//        a.pb(rand()%n); b.pb(rand()%n);
//        if (a[0] > b[0]) swap(a[0], b[0]);
//        vector<ll> fast = minimum_costs(h,a,b);
//        vector<ll> slow = mc2(h,a,b);
//        if( fast != slow) {
//            for (int t : h) cout<<t<<' ';
//            cout<<endl;
//            cout<<a[0]<<' '<<b[0]<<endl;
//            bug(fast[0], slow[0]);
//            assert(0);
//        }
//    }
//}

/*
6 3
1 2 1 1 2 1
0 5
1 2
2 4
*/

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