Submission #707216

#	Time	Username	Problem	Language	Result	Execution time	Memory
707216		lam	Meetings (IOI18_meetings)	C++14	0 / 100	18 ms	38124 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
#define int long long
using namespace std;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
#define ff first
#define ss second
const int maxn = 8e5 + 10;
const int inf = 1e18;
int n,q;
deque<int> dq;
vector <int> adj[maxn];
int in[maxn],out[maxn],cnt;
int par[21][maxn];
int h[maxn];
ii range[maxn];
vector <iii> queries[maxn];
int res[maxn];
struct line
{
    int a,b;
};
int calc(line x, int idx)
{
    return x.a*idx + x.b;
}
struct segtree
{
    line f[4*maxn], lazy[4*maxn];
    void pushsum(int x, int lx, int rx, line val)
    {
        f[x].a += val.a; f[x].b += val.b;
        lazy[x].a += val.a; lazy[x].b += val.b;
    }
    void downsum(int x, int lx, int rx)
    {
        if (lx==rx) return;
        int mid=(lx+rx)/2;
        if (lazy[x].a!=0||lazy[x].b!=0)
        {
            pushsum(2*x,lx,mid,lazy[x]);
            pushsum(2*x+1,mid+1,rx,lazy[x]);
            lazy[x]={0,0};
        }
    }
    void update(int x, int lx, int rx, line val)
    {
        if (lx==rx)
        {
            if (calc(f[x],lx)>calc(val,lx)) swap(f[x],val);
            return;
        }
        int mid=(lx+rx)/2;
        downsum(x,lx,rx);
        if (calc(f[x],mid)>calc(val,mid)) swap(f[x],val);
        if (calc(f[x],lx)>calc(val,lx)) update(2*x,lx,mid,val);
        else update(2*x+1,mid+1,rx,val);
    }
    void downline(int x, int lx, int rx)
    {
        if (lx==rx) return;
        int mid=(lx+rx)/2;
        update(2*x,lx,mid,f[x]);
        update(2*x+1,mid+1,rx,f[x]);
        f[x]={0,inf};
    }
    void update_min(int x, int lx, int rx, int l, int r, line val)
    {
        if (lx>r||rx<l) return;
        if (lx>=l&&rx<=r)
        {
            update(x,lx,rx,val);
            return;
        }
        int mid=(lx+rx)/2;
        downsum(x,lx,rx);
        update_min(2*x,lx,mid,l,r,val);
        update_min(2*x+1,mid+1,rx,l,r,val);
    }
    void add(int x, int lx, int rx, int l, int r, line val)
    {
        if (lx>r||rx<l) return;
        if (lx>=l&&rx<=r)
        {
            pushsum(x,lx,rx,val);
            return;
        }
        int mid=(lx+rx)/2;
        downsum(x,lx,rx);
        downline(x,lx,rx);
        add(2*x,lx,mid,l,r,val);
        add(2*x+1,mid+1,rx,l,r,val);
    }
    int qry(int x, int lx, int rx, int idx)
    {
        if (lx==rx) return calc(f[x],lx);
        int mid=(lx+rx)/2;
        downsum(x,lx,rx);
        int temp = calc(f[x],idx);
        if (idx<=mid) return min(temp,qry(2*x,lx,mid,idx));
        else return min(temp,qry(2*x+1,mid+1,rx,idx));
    }
    void build(int x, int lx, int rx)
    {
        lazy[x]={0,0};
        f[x]={0,0};
        if (lx==rx) return;
        int mid=(lx+rx)/2;
        build(2*x,lx,mid); build(2*x+1,mid+1,rx);
    }
};
segtree pre,suf;

void dfs(int x, int p)
{
    par[0][x]=p;
    for (int i=1; i<=20; i++) par[i][x]=par[i-1][par[i-1][x]];
    in[x]=++cnt;
    for (int i:adj[x])
        if (i!=p) dfs(i,x);
    out[x]=cnt;
}

bool check(int u, int v)
{
    return in[u]<=in[v]&&out[v]<=out[u];
}

int lca(int u, int v)
{
    if (check(u,v)) return u;
    if (check(v,u)) return v;
    for (int i=20; i>=0; i--)
        if (!check(par[i][u],v)) u=par[i][u];
    return par[0][u];
}

bool cmp(int x, int y)
{
    if (h[x]!=h[y]) return h[x]<h[y];
    return x>y;
}

vector<long long> minimum_costs(vector<int32_t> H, vector<int32_t> L,
                                     vector<int32_t> R) {
    n=H.size(); q=L.size();
    for (int i=1; i<=n; i++) h[i]=H[i-1];
    for (int i=1; i<=n; i++)
    {
        while (!dq.empty()&&h[dq.back()]<h[i]) dq.pop_back();
        if (!dq.empty()) adj[dq.back()].push_back(i), range[i].ff = dq.back()+1;
        else range[i].ff=1;
        dq.push_back(i);
    }
    while (!dq.empty()) dq.pop_back();
    for (int i=n; i>=1; i--)
    {
        while (!dq.empty()&&h[dq.back()]<=h[i]) dq.pop_back();
        if (!dq.empty()) adj[dq.back()].push_back(i), range[i].ss = dq.back()-1;
        else range[i].ss=n;
        dq.push_back(i);
    }
    int root = -1;
    for (int i=1; i<=n; i++)
        if (range[i].ff==1&&range[i].ss==n) root=i;
    dfs(root,root);
    for (int i=1; i<=q; i++)
    {
        int l,r; l=L[i-1]; r=R[i-1];
        int x = lca(l,r);
        queries[x].push_back({{l,r},i});
    }
    vector <int> id;
    for (int i=1; i<=n; i++) id.push_back(i);
    sort(id.begin(),id.end(),cmp);
    pre.build(1,1,n);
    suf.build(1,1,n);
    for (int it:id)
    {
        int ll = range[it].ff; int rr=range[it].ss;
//        cout<<it<<" == "<<ll<<' '<<rr<<'\n';
        for (iii i:queries[it])
        {
            int ans = 1e18;
            if (i.ff.ff<it) ans = min(ans,suf.qry(1,1,n,i.ff.ff) + (i.ff.ss-it+1)*h[it]);
            if (i.ff.ss>it) ans = min(ans,pre.qry(1,1,n,i.ff.ss) + (it-i.ff.ff+1)*h[it]);
            if (i.ff.ff==it&&i.ff.ss==it) ans = h[it];
            res[i.ss]=ans;
        }
        int x = suf.qry(1,1,n,ll);
        int y = pre.qry(1,1,n,rr);
        suf.add(1,1,n,ll,it,{0,(rr-it+1)*h[it]});
        pre.add(1,1,n,it,rr,{0,(it-ll+1)*h[it]});
        suf.update_min(1,1,n,ll,it,{-h[it],(it+1)*h[it] + y});
        pre.update_min(1,1,n,it,rr,{h[it],x - (it-1)*h[it]});
//        cout<<it<<" !!\n";
//        cout<<"pre "; for (int j=1; j<=n; j++) cout<<pre.qry(1,1,n,j)<<' '; cout<<'\n';
//        cout<<"suf "; for (int j=1; j<=n; j++) cout<<suf.qry(1,1,n,j)<<' '; cout<<'\n';
//        cout<<"----\n";
    }
    vector <long long> rres;
    for (int i=1; i<=q; i++)  rres.push_back(res[i]);
    return rres;
}

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