Submission #236314

#	Time	Username	Problem	Language	Result	Execution time	Memory
236314		lyc	Meetings (IOI18_meetings)	C++14	100 / 100	2423 ms	415380 KiB

meetings

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

#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
typedef long long ll;

const int mxN = 750005;
const int lgN = 19;
const int mxQ = 750005;
int N, Q;
vector<int> H;
struct SparseTable {
    int A[mxN][lgN+1];
    void init(vector<int>& H) {
        FOR(i,0,N-1){ A[i][0] = i; }
        FOR(k,1,lgN){
            FOR(i,0,N-(1<<k)){
                int p = A[i][k-1], q = A[i+(1<<(k-1))][k-1];
                A[i][k] = (H[p] > H[q] ? p : q);
            }
        }
    }
    int query(int l, int r) {
        int k = floor(log2(r-l+1));
        int i = A[l][k], j = A[r-(1<<k)+1][k];
        return H[i] > H[j] ? i : j;
    }
} st;
struct Query { int l, r, i; }; vector<Query> query[mxN];
vector<ll> ans;
ll f(int x, ll m, ll c) { return x*m + c; }
struct SegmentTree {
    ll vl[4*mxN], vr[4*mxN], tagM[4*mxN], tagC[4*mxN], add[4*mxN]; bool tag[4*mxN];
    int n;
    void build(int _n) {
        n = _n;
        //fill_n(D,4*n,(Node){0,0,0,0,0,0});
    }
    void replace(int s, int e, int p, ll m, ll c) {
        vl[p] = f(s,m,c);
        vr[p] = f(e,m,c);
        tagM[p] = m;
        tagC[p] = c;
        add[p] = 0;
        tag[p] = true;
    }
    void addTo(int p, ll v) {
        vl[p] += v;
        vr[p] += v;
        add[p] += v;
    }
    void prop(int s, int e, int p) {
        if (tag[p]) {
            if (s != e) {
                int mid = (s+e)/2;
                replace(s,mid,p<<1,tagM[p],tagC[p]);
                replace(mid+1,e,p<<1|1,tagM[p],tagC[p]);
            }
            tag[p] = false;
        }
        if (add[p]) {
            if (s != e) {
                addTo(p<<1,add[p]);
                addTo(p<<1|1,add[p]);
            }
            add[p] = 0;
        }
    }
    void update(int s, int e, int p, int x, int y, ll m, ll c, ll v) {
        if (x > y) return;
        if (s >= x && e <= y) {
            if (f(s,m,c) <= vl[p] + v && f(e,m,c) <= vr[p] + v) return replace(s,e,p,m,c);
            if (vl[p] + v < f(s,m,c) && vr[p] + v < f(e,m,c)) return addTo(p,v);
        }
        int mid = (s+e)/2;
        assert(s != e);
        prop(s,e,p);
        if (mid >= x) update(s,mid,p<<1,x,y,m,c,v);
        if (mid < y) update(mid+1,e,p<<1|1,x,y,m,c,v);
        vl[p] = vl[p<<1];
        vr[p] = vr[p<<1|1];
    }
    inline void update(int x, int y, ll m, ll c, ll v) { return update(0,N-1,1,x,y,m,c,v); }
    ll query(int s, int e, int p, int x) {
        if (s == e) {
            return vl[p];
        } else {
            int mid = (s+e)/2;
            prop(s,e,p);
            if (x <= mid) return query(s,mid,p<<1,x);
            else return query(mid+1,e,p<<1|1,x);
        }
    }
    inline ll query(int x) { return query(0,N-1,1,x); }
} fixr, fixl;

void solve(int l, int r) {
    if (l > r) return;
    int p = st.query(l,r);
    solve(l,p-1);
    solve(p+1,r);
    for (Query q : query[p]) {
        ans[q.i] = (ll) (q.r-q.l+1) * H[p];
        if (q.l < p) ans[q.i] = min(ans[q.i], fixr.query(q.l) + (ll) (q.r-p+1) * H[p]);
        if (q.r > p) ans[q.i] = min(ans[q.i], fixl.query(q.r) + (ll) (p-q.l+1) * H[p]);
    }
    // f(l,p-1) + (i-p+1) * H[p]
    // f(p+1,i) + (p-l+1) * H[p]
    ll lv = (p > l ? fixl.query(p-1) : 0);
    fixl.update(p,r, H[p], lv+(ll)(-p+1)*H[p], (ll)(p-l+1)*H[p]);
    // f(p+1,r) + (p-i+1) * H[p]
    // f(i,p-1) + (r-p+1) * H[p]
    ll rv = (p < r ? fixr.query(p+1) : 0);
    fixr.update(l,p, -H[p], rv+(ll)(p+1)*H[p], (ll)(r-p+1)*H[p]);
}

std::vector<long long> minimum_costs(std::vector<int> _H, std::vector<int> L,
        std::vector<int> R) {
    H = _H;
    N = SZ(H);
    Q = SZ(L);

    st.init(H);

    FOR(i,0,Q-1){
        int p = st.query(L[i],R[i]);
        query[p].push_back({L[i],R[i],i});
    }

    ans.assign(Q,0);
    fixl.build(N);
    fixr.build(N);
    solve(0,N-1);

    return ans;
}

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