Submission #426029

#	Time	Username	Problem	Language	Result	Execution time	Memory
426029		Peti	Meetings (IOI18_meetings)	C++14	60 / 100	5604 ms	335008 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"

#pragma GCC optimize("Ofast")

using namespace std;

const long long INF = (long long)1e18;

struct segment_tree{
    vector<int> st, v;
    int maxn;

    int get(int x, int y){
        if(x == maxn) return y;
        if(y == maxn) return x;
        return v[x] >= v[y] ? x : y;
    }

    void init(vector<int> ert, int n){
        maxn = n;
        while(maxn != (maxn&(-maxn))) maxn += (maxn&(-maxn));
        v = ert;
        st.resize(maxn<<1, maxn);
        iota(st.begin()+maxn, st.begin()+maxn+n, 0);
        for(int i = maxn-1; i > 0; i--)
            st[i] = get(st[2*i], st[2*i+1]);
    }

    int query(int s, int e, int x, int l, int r){
        if(e <= l || r <= s)
            return maxn;
        if(s <= l && r <= e)
            return st[x];
        int m = (l+r)/2;
        return get(query(s, e, 2*x, l, m), query(s, e, 2*x+1, m, r));
    }

    int query(int l, int r){
        return query(l, r, 1, 0, maxn);
    }
};

struct egyenes{
    long long m, b;
    egyenes(){}
    egyenes(long long m, long long b) : m(m), b(b) {}
    long long ertek(long long x) { return m*x+b; }
};

struct lichao_tree{
    vector<egyenes> st;
    vector<long long> prop;
    int maxn;

    void init(int n){
        maxn = n;
        while(maxn != (maxn&(-maxn))) maxn += (maxn&(-maxn));
        st.assign(maxn<<1, egyenes(0, INF));
        prop.assign(maxn<<1, 0);
    }

    void propagate(int x){
        st[x].b += prop[x];
        if(x < maxn){
            prop[2*x] += prop[x];
            prop[2*x+1] += prop[x];
        }
        prop[x] = 0;
    }


    void add(egyenes e, int x, int l, int r){
        if(e.m == 0ll) return;
        propagate(x);
        int m = (l+r)/2;
        bool bal = e.ertek(l) < st[x].ertek(l);
        bool koz = e.ertek(m) < st[x].ertek(m);
        if(koz) swap(st[x], e);
        if(l+1 == r) return;
        if(bal == koz)
            add(e, 2*x+1, m, r);
        else
            add(e, 2*x, l, m);
    }

    void update(int s, int e, egyenes eg, int x, int l, int r){
        propagate(x);
        if(e <= l || r <= s)
            return;
        if(s <= l && r <= e){
            add(eg, x, l, r);
            return;
        }
        int m = (l+r)/2;
        update(s, e, eg, 2*x, l, m);
        update(s, e, eg, 2*x+1, m, r);
    }

    void update(int l, int r, egyenes e) { update(l, r, e, 1, 0, maxn); }

    void update_lines(int s, int e, long long c, int x, int l, int r){
        propagate(x);
        if(e <= l || r <= s)
            return;
        if(s <= l && r <= e){
            prop[x] += c;
            return;
        }
        int m = (l+r)/2;
        update_lines(s, e, c, 2*x, l, m);
        update_lines(s, e, c, 2*x+1, m, r);
    }

    void update_lines(int l, int r, long long c) { update_lines(l, r, c, 1, 0, maxn); }

    long long query(int ind, int x, int l, int r){
        propagate(x);
        if(l+1 == r)
            return st[x].ertek(ind);
        int m = (l+r)/2;
        if(ind < m)
            return min(st[x].ertek(ind), query(ind, 2*x, l, m));
        return min(st[x].ertek(ind), query(ind, 2*x+1, m, r));
    }

    long long query(int x) { return query(x, 1, 0, maxn); }
};

struct adat{
    int ind, l, r;
};

/*struct node{
    int l, r, lc, rc;
    long long ert;
    vector<adat> querys;
    node *L = nullptr, *R = nullptr;

    node(){}
    node(node *L, node *R, int l, int r, int lc, int rc) : L(L), R(R), l(l), r(r), lc(lc), rc(rc) {};
};
typedef node* gnode;*/

struct gnode{
    int l, r, lc, rc;
    long long ert;
};

segment_tree maxST;
lichao_tree lichao;
vector<int> h;

/*void kiir(gnode p){
    cout<<"node: ("<<(p->l)<<", "<<(p->r)<<")  ert: "<<p->ert<<"  cl: "<<p->lc<<"  cr: "<<p->rc<<"\n";
}*/
vector<vector<adat>> vegek((int)1e6);
vector<long long> meg;

int starts[(int)1e6];
vector<adat> buffer[(int)1e6];

void add_node(gnode os, gnode p, int ind){
    long long ossz = (long long)(p.r-p.l)*p.rc;
    if(h[p.l] > p.rc) ossz += (long long)(h[p.l] - p.rc);
    lichao.update_lines(p.r, os.r, ossz);
    lichao.update(p.r, os.r, {p.rc, p.ert-(long long)p.rc*p.r});
    return;
}

long long build(int l, int r, int lc, int rc, int len){
    if(l+1 == r){
        for(adat d : vegek[l]){
            int m = lower_bound(starts, starts+len, d.l)-starts;
            if(m == len) continue;
            buffer[m].push_back(d);
        }
        return h[l];
    }
    int m = maxST.query(l, r);
    int c = h[m];
    starts[len] = l;
    buffer[len].clear();
    if(m == l) m++;

    long long lb = build(l, m, lc, c, len+1);
    long long rb = build(m, r, c, rc, len+1);

    long long ert = min(lb + (long long)(r-m)*c, rb + (long long)(m-l)*c);
    add_node({l, r, lc, rc, ert}, {l, m, lc, c, lb}, len);

    for(adat d : buffer[len]){
        meg[d.ind] = min(meg[d.ind], lichao.query(d.r+1) + (long long)(l-d.l)*lc);
    }

    return ert;
}

/*void bejar(gnode p, int len){
    if(p->l+1 == p->r){
        return;
    }
    bejar(p->L, len);
    bejar(p->R, len+1);
}*/

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
    H.push_back((int)1e9+1);
    H.insert(H.begin(), (int)1e9+1);
    int n = (int)H.size();
    int q = (int)L.size();
    h = H;
    meg.assign(q, INF);
    vegek.assign((int)1e6, vector<adat>());

    maxST.init(H, n);
    lichao.init(n);
    for(int i = 0; i < q; i++)
        vegek[R[i]+2].push_back({i, L[i]+1, R[i]+1});
    build(0, n, 0, 0, 0);

    for(int i = 0; i < q; i++)
        vegek[R[i]+2].clear();

    reverse(h.begin(), h.end());
    maxST.init(h, n);
    for(int i = 0; i < q; i++)
        vegek[n-L[i]-1].push_back({i, n-R[i]-2, n-L[i]-2});
    build(0, n, 0, 0, 0);

    return meg;
}

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