Submission #807074

#	Time	Username	Problem	Language	Result	Execution time	Memory
807074		fatemetmhr	Meetings (IOI18_meetings)	C++17	100 / 100	5361 ms	786432 KiB

meetings

// Be name khode //

#include "meetings.h"
#pragma GCC optimize ("O0")
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define mp     make_pair
#define fi     first
#define se     second
#define pb     push_back

typedef long long ll;

const int maxn5 = 75e4 + 5;
const int maxnt = 4e6  + 5;
const int lg    = 20;
const ll  inf   = 1e18;

int n, newnode = 2, curpt = 0;
vector <ll> ret;
ll a[maxn5];

pair <ll, pair<ll, ll>> av[maxn5 * lg * 2];

namespace rmq{
    pair <int, int> mx[lg][maxn5];
    void build(int n){
        for(int i = 1; i < lg; i++) for(int j = 0; j < n; j++)
            mx[i][j] = max(mx[i - 1][j], (j + (1 << (i - 1))) < n ? mx[i - 1][j + (1 << (i - 1))] : mp(-1, -1));
    }

    int get_max(int l, int r){
        int k = 31 - __builtin_clz(r - l + 1);
        return max(mx[k][l], mx[k][r - (1 << k) + 1]).se;
    }

}

struct cht{
    int ptl = 0, ptr = 0;

    ll inter(pair <ll, ll> a, pair <ll, ll> b){
        if(a.se == b.se)
            return a.fi > b.fi ? inf : -inf;
        //cout << a.fi << ' ' << a.se << ' ' << b.fi << ' ' << b.se << endl;
        return (a.fi - b.fi) / (b.se - a.se) + ((a.fi - b.fi) % (b.se - a.se) > 0);
    }

    void add(ll cons, ll sh){
        ll st = -inf;
        while(ptr > ptl && (st = inter(av[ptr - 1].se, mp(cons, sh))) <= av[ptr - 1].fi)
            ptr--;
        if(ptr == ptl)
            st = -inf;
        //cout << "ha? " << cons << ' ' << sh << ' ' << st << ' ' << av.size() << endl;
        //cout << (-122) / 46 << endl;
        //cout << "ha? " << cons << ' ' << sh << ' ' << ptr << ' ' << av.size() << endl;
        av[ptr++] = {st, {cons, sh}};
    }

    ll get(ll x){
        if(ptl == ptr)
            return -inf;
        int pt2 = upper_bound(av + ptl, av + ptr, mp(x, mp(inf, inf))) - av - 1;
        //cout << "we all gor " << pt << ' ' << av[pt].se.fi << ' ' << av[pt].se.se << ' ' << av.size() << endl;
        //cout << av.back().fi << ' ' << x << endl;
        //cout << av.back().se.fi << ' ' << av.back().se.se << endl;
        return av[pt2].se.fi + av[pt2].se.se * x;
    }

} seg[maxnt];

int ch[2][maxnt], cnt[maxnt];
ll lazy[maxnt];

struct segment{


    segment(){
        memset(lazy, 0, sizeof lazy);
    }

    void build(int l, int r, int v){
        cnt[v] += (r - l == 1);
        seg[v].ptl = seg[v].ptr = curpt;
        curpt += cnt[v];
        if(curpt >= maxn5 * lg * 2)
            exit(0);
        if(r - l == 1){
            seg[v].add(0, 0);
            return;
        }
        int mid = (l + r) >> 1;
        if(!ch[0][v])
            ch[0][v] = newnode++;
        if(!ch[1][v])
            ch[1][v] = newnode++;
        build(l, mid, ch[0][v]);
        build(mid, r, ch[1][v]);
    }

    void sch(int l, int r, int lq, int rq, int v){
        if(rq <= l || r <= lq)
            return;
        if(lq <= l && r <= rq){
            cnt[v]++;
            return;
        }
        int mid = (l + r) >> 1;
        if(!ch[0][v])
            ch[0][v] = newnode++;
        if(!ch[1][v])
            ch[1][v] = newnode++;
        sch(l, mid, lq, rq, ch[0][v]);
        sch(mid, r, lq, rq, ch[1][v]);
    }

    void add_cht(int l, int r, int lq, int rq, pair <ll, ll> val, int v){
        if(rq <= l || r <= lq)
            return;
        //cout << "there's " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << val.fi << ' ' << val.se << ' ' << v << ' ' << lazy[v] << endl;
        val.fi += lazy[v];
        if(lq <= l && r <= rq){
            //cout << "baba " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << v << ' ' << cnt[v] << ' ' << val.fi << ' ' << val.se << endl;
            seg[v].add(val.fi, val.se);
            return;
        }
        int mid = (l + r) >> 1;
        add_cht(l, mid, lq, rq, val, ch[0][v]);
        add_cht(mid, r, lq, rq, val, ch[1][v]);
    }

    void add(int l, int r, int lq, int rq, ll val, int v){
        if(rq <= l || r <= lq)
            return;
        //cout << "adding " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << val << ' ' << v << endl;
        if(lq <= l && r <= rq){
            lazy[v] += val;
            return;
        }
        int mid = (l + r) >> 1;
        add(l, mid, lq, rq, val, ch[0][v]);
        add(mid, r, lq, rq, val, ch[1][v]);
    }

    ll get(int l, int r, int id, int v){
        ll ret = (-seg[v].get(id)) + lazy[v];
        //cout << "look " << l << ' ' << r << ' ' << v << ' '  << ret << ' ' << lazy[v] << ' ' << id << endl;
        if(r - l == 1)
            return ret;
        int mid = (l + r) >> 1;
        if(abs(id) < mid)
            ret = min(ret, get(l, mid, id, ch[0][v]) + lazy[v]);
        else
            ret = min(ret, get(mid, r, id, ch[1][v]) + lazy[v]);
        //cout << "fina " << l << ' ' << r << ' ' << ret << ' ' << lazy[v] << endl;
        return ret;
    }

} pre, suf;

vector <pair<pair<int, int>, int>> req[maxn5];

void cartesian(int l, int r){
    if(r - l == 1){
        for(auto [p, id] : req[l])
            ret[id] = a[l];
        pre.add(0, n, l, l + 1, a[l], 0);
        suf.add(0, n, l, l + 1, a[l], 1);
        return;
    }
    int mx = rmq::get_max(l, r - 1);
    if(l < mx)
        cartesian(l, mx);
    if(mx + 1 < r)
        cartesian(mx + 1, r);
    //cout << "in " << l << ' ' << r << ' ' << mx << endl;
    for(auto [p, id] : req[mx]){
        int lq = p.fi, rq = p.se;
        ret[id] = (rq - lq + 1) * a[mx];
        //cout << ret[id] << endl;
        if(lq < mx)
            ret[id] = min(ret[id], suf.get(0, n, lq, 1) + (rq - mx + 1) * a[mx]);
        //cout << ret[id]  << endl;
        if(rq > mx)
            ret[id] = min(ret[id], pre.get(0, n, -rq, 0) + (mx - lq + 1) * a[mx]);
        //cout << ret[id]  << endl;
    }
    ll keeppre = (l < mx ? pre.get(0, n, -(mx - 1), 0) : 0);
    ll keepsuf = (mx + 1 < r ? suf.get(0, n, mx + 1, 1) : 0);
    //cout << "in " << l << ' ' << r << ' ' << mx << ' ' << keepsuf << ' ' << keeppre << endl;
    pre.add(0, n, mx, r, (mx - l + 1) * a[mx], 0);
    suf.add(0, n, l, mx + 1, (r - mx) * a[mx], 1);
    pre.add_cht(0, n, mx, r, mp(-(keeppre + (1 - mx) * a[mx]), a[mx]), 0);
    //cout << "all here " << endl;
    suf.add_cht(0, n, l, mx + 1, mp(-(keepsuf + (1 + mx) * a[mx]), a[mx]), 1);
    //cout << "all done " << l << ' ' << r << endl;
}

void pre_cartesian(int l, int r){
    if(r - l <= 1)
        return;
    int mid = rmq::get_max(l, r - 1);
    pre_cartesian(l, mid);
    pre_cartesian(mid + 1, r);
    pre.sch(0, n, mid, r, 0);
    suf.sch(0, n, l, mid + 1, 1);
}


std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> l,
                                     std::vector<int> r) {
    n = h.size();
    for(int i = 0; i < n; i++)
        a[i] = h[i];
    int q = l.size();
    ret.resize(q);
    for(int i = 0; i < n; i++)
        rmq::mx[0][i] = mp(h[i], i);
    rmq::build(n);
    for(int i = 0; i < q; i++){
        int mx = rmq::get_max(l[i], r[i]);
        req[mx].pb({{l[i], r[i]}, i});
    }
    pre_cartesian(0, n);
    pre.build(0, n, 0);
    suf.build(0, n, 1);
    cartesian(0, n);
    return ret;
}

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