Submission #978696

#	Time	Username	Problem	Language	Result	Execution time	Memory
978696		12345678	Meetings (IOI18_meetings)	C++17	100 / 100	3170 ms	375068 KiB

meetings

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

#define ll long long

using namespace std;

const int nx=750005, kx=20;

int n, q, h[nx], ql[nx], qr[nx], l[nx], r[nx], rt, lvl[nx], pa[nx][kx], mn[nx], mx[nx];
vector<int> qrs[nx];
vector<ll> res;

struct line
{
    ll m, c;
    line(ll m=0, ll c=1e18): m(m), c(c){}
    ll val(ll x) {return m*x+c;}
};

struct lichaotree
{
    line d[4*nx];
    ll lz[4*nx];
    void pushlz(int l, int r, int i)
    {
        d[i].c+=lz[i];
        if (l!=r) lz[2*i]+=lz[i], lz[2*i+1]+=lz[i];
        lz[i]=0;
    }
    void update(int l, int r, int i, int ql, int qr, line x)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        int md=(l+r)/2;
        if (ql<=l&&r<=qr)
        {
            if (x.val(md)<d[i].val(md)) swap(x, d[i]);
            if (d[i].val(l)>x.val(l)) update(l, md, 2*i, ql, qr, x);
            if (d[i].val(r)>x.val(r)) update(md+1, r, 2*i+1, ql, qr, x);
        }
        else
        {
            update(l, md, 2*i, ql, qr, x);
            update(md+1, r, 2*i+1, ql, qr, x);
        }
    }
    void update2(int l, int r, int i, int ql, int qr, ll vl)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return lz[i]+=vl, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update2(l, md, 2*i, ql, qr, vl);
        update2(md+1, r, 2*i+1, ql, qr, vl);
    }
    ll query(int l, int r, int i, int idx)
    {
        pushlz(l, r, i);
        if (l==r) return d[i].val(idx);
        int md=(l+r)/2;
        if (idx<=md) return min(d[i].val(idx), query(l, md, 2*i, idx));
        else return min(d[i].val(idx), query(md+1, r, 2*i+1, idx));
    }
} sl, sr;

void dfs(int u, int p)
{
    mn[u]=mx[u]=u;
    lvl[u]=lvl[p]+1;
    pa[u][0]=p;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    if (l[u]) dfs(l[u], u), mn[u]=mn[l[u]];
    if (r[u]) dfs(r[u], u), mx[u]=mx[r[u]];
}

int lca(int u, int v)
{
    if (lvl[u]>lvl[v]) swap(u, v);
    for (int i=kx-1; i>=0; i--) if (lvl[u]<=lvl[pa[v][i]]) v=pa[v][i];
    if (u==v) return u;
    for (int i=kx-1; i>=0; i--) if (pa[u][i]!=pa[v][i]) u=pa[u][i], v=pa[v][i];
    return pa[u][0];
}

void dfs2(int u)
{
    if (l[u]) dfs2(l[u]);
    if (r[u]) dfs2(r[u]);
    sl.update(1, n, 1, u, u, line(0, 0));
    sr.update(1, n, 1, u, u, line(0, 0));
    for (auto idx:qrs[u]) res[idx]=min(sl.query(1, n, 1, ql[idx])+(ll)(qr[idx]-u+1)*h[u], sr.query(1, n, 1, qr[idx])+(ll)(u-ql[idx]+1)*h[u]);
    sl.update2(1, n, 1, mn[u], u, (ll)(mx[u]-u+1)*h[u]);
    if (u!=mx[u]) sl.update(1, n, 1, mn[u], u, line(-h[u], sl.query(1, n, 1, u+1)+((ll)(u+1))*h[u]));
    sr.update2(1, n, 1, u, mx[u], (ll)(u-mn[u]+1)*h[u]);
    if (u!=mn[u]) sr.update(1, n, 1, u, mx[u], line(h[u], sr.query(1, n, 1, u-1)-((ll)(u-1))*h[u]));
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
    n=H.size();
    q=L.size();
    res.resize(q);
    for (int i=1; i<=n; i++) h[i]=H[i-1];
    for (int i=0; i<q; i++) ql[i]=L[i]+1, qr[i]=R[i]+1;
    stack<int> s;
    for (int i=1; i<=n; i++)
    {
        while (!s.empty()&&h[s.top()]<h[i]) l[i]=s.top(), s.pop();
        if (!s.empty()) r[s.top()]=i;
        else rt=i;
        s.push(i);
    }
    //for (int i=1; i<=n; i++) cout<<"cartesian "<<i<<' '<<l[i]<<' '<<r[i]<<'\n';
    dfs(rt, rt);
    for (int i=0; i<q; i++) qrs[lca(ql[i], qr[i])].push_back(i); //cout<<"debug "<<i<<' '<<ql[i]<<' '<<qr[i]<<' '<<lca(ql[i], qr[i])<<'\n';
    dfs2(rt);
    return res;
}

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