Submission #883200

#	Time	Username	Problem	Language	Result	Execution time	Memory
883200		andrei_boaca	Meetings (IOI18_meetings)	C++17	0 / 100	36 ms	91220 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
int iteration;
ll n,q,v[750005],rmq[21][750005];
ll loga[750005];
vector<ll> sol;
ll best(ll i,ll j)
{
    if(v[i]>v[j])
        return i;
    if(v[j]>v[i])
        return j;
    if(iteration==1)
        return max(i,j);
    else
        return min(i,j);
}
ll getbest(ll l,ll r)
{
    ll lg=loga[r-l+1];
    return best(rmq[lg][l],rmq[lg][r-(1<<lg)+1]);
}
struct query
{
    ll r,ind,cst;
};
vector<query> who[750005];
struct interv
{
    ll st,dr,a,b;
};
struct node
{
    node *l;
    node *r;
    deque<interv> s;
    ll lazy;
    node()
    {
        lazy=0;
        l=NULL;
        r=NULL;
    }
};
ll eval(node *me, ll poz)
{
    ll st=0;
    ll dr=me->s.size();
    dr--;
    while(st<=dr)
    {
        ll mij=(st+dr)/2;
        if(me->s[mij].st>poz)
        {
            dr=mij-1;
            continue;
        }
        if(me->s[mij].dr<poz)
        {
            st=mij+1;
            continue;
        }
        ll val=me->s[mij].a*poz+me->s[mij].b+me->lazy;
        return val;
    }
}
node* build(ll l,ll r)
{
    ll poz=getbest(l,r);
    ll hv=v[poz];
    node *nod = new node;
    if(l<=poz-1)
        nod->l=build(l,poz-1);
    if(r>=poz+1)
        nod->r=build(poz+1,r);
    ll valmij=0;
    if(nod->l==NULL)
    {
        valmij=v[poz];
        nod->l=new node;
    }
    else
        valmij=eval(nod->l,poz-1)+v[poz];
    nod->l->s.push_back({l,r,0,valmij-nod->l->lazy});
    ll off=hv*(poz-l+1);
    if(nod->r==NULL)
    {
        nod=nod->l;
        for(auto i:who[l])
        {
            ll rgt=i.r;
            ll ind=i.ind;
            ll cst=i.cst;
            if(rgt<=r)
            {
                ll val=eval(nod,rgt)+cst;
                sol[ind]=min(sol[ind],val);
            }
        }
        return nod;
    }
    valmij-=hv*poz;
    nod->r->lazy+=off;
    while(!nod->r->s.empty())
    {
        interv a=nod->r->s.front();
        ll p=a.dr;
        ll val1=valmij+hv*p;
        ll val2=a.a*p+a.b+nod->r->lazy;
        if(val1<=val2)
        {
            nod->r->s.pop_front();
            continue;
        }
        else
        {
            ll st=a.st;
            ll dr=a.dr;
            ll j=p;
            while(st<=dr)
            {
                ll mij=(st+dr)/2;
                val1=valmij+hv*mij;
                val2=a.a*mij+a.b+nod->r->lazy;
                if(val1>val2)
                {
                    j=mij;
                    dr=mij-1;
                }
                else
                    st=mij+1;
            }
            nod->r->s.pop_front();
            a.st=j+1;
            nod->r->s.push_front(a);
            interv add={poz+1,j,hv,valmij-nod->r->lazy};
            nod->r->s.push_front(add);
            break;
        }
    }
    if(nod->r->s.empty())
        nod->r->s.push_back({poz+1,r,hv,valmij-nod->r->lazy});
    node *rez;
    if(nod->l->s.size()<nod->r->s.size())
    {
        ll dif=nod->r->lazy-nod->l->lazy;
        rez=nod->r;
        while(!nod->l->s.empty())
        {
            interv a=nod->l->s.back();
            nod->l->s.pop_back();
            a.b-=dif;
            rez->s.push_front(a);
        }
        return rez;
    }
    else
    {
        ll dif=nod->l->lazy-nod->r->lazy;
        rez=nod->l;
        while(!nod->r->s.empty())
        {
            interv a=nod->r->s.front();
            nod->r->s.pop_front();
            a.b-=dif;
            rez->s.push_back(a);
        }
    }
    for(auto i:who[l])
    {
        ll rgt=i.r;
        ll ind=i.ind;
        ll cst=i.cst;
        if(rgt<=r)
        {
            ll val=eval(rez,rgt)+cst;
            sol[ind]=min(sol[ind],val);
        }
    }
    return rez;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
    n=H.size();
    q=L.size();
    sol.resize(q);
    iteration=1;
    for(int i=1;i<=n;i++)
    {
        v[i]=H[i-1];
        for(int bit=0;bit<=20;bit++)
            if((1<<bit)<=i)
                loga[i]=bit;
    }
    for(int i=0;i<q;i++)
    {
        sol[i]=1e17;
        L[i]++;
        R[i]++;
    }
    for(int i=n;i>=1;i--)
    {
        rmq[0][i]=i;
        for(int j=1;j<=20;j++)
        {
            rmq[j][i]=rmq[j-1][i];
            int poz=i+(1<<(j-1));
            if(poz<=n)
                rmq[j][i]=best(rmq[j][i],rmq[j-1][poz]);
        }
    }
    for(int i=0;i<q;i++)
    {
        ll poz=getbest(L[i],R[i]);
        ll cst=(poz-L[i]+1)*v[poz];
        if(poz+1<=R[i])
            who[poz+1].push_back({R[i],i,cst});
        else
            sol[i]=min(sol[i],cst);
    }
    build(1,n);
    iteration=2;
    reverse(v+1,v+n+1);
    for(int i=1;i<=n;i++)
        who[i].clear();
    for(int i=0;i<q;i++)
    {
        L[i]=n-L[i]+1;
        R[i]=n-R[i]+1;
        swap(L[i],R[i]);
    }
    for(int i=n;i>=1;i--)
    {
        rmq[0][i]=i;
        for(int j=1;j<=20;j++)
        {
            rmq[j][i]=rmq[j-1][i];
            int poz=i+(1<<(j-1));
            if(poz<=n)
                rmq[j][i]=best(rmq[j][i],rmq[j-1][poz]);
        }
    }
    for(int i=0;i<q;i++)
    {
        ll lft=L[i];
        ll rgt=R[i];
        ll poz=getbest(L[i],R[i]);
        ll cst=(poz-L[i]+1)*v[poz];
        if(poz+1<=R[i])
            who[poz+1].push_back({R[i],i,cst});
        else
            sol[i]=min(sol[i],cst);
    }
    build(1,n);
    return sol;
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:248:12: warning: unused variable 'lft' [-Wunused-variable]
  248 |         ll lft=L[i];
      |            ^~~
meetings.cpp:249:12: warning: unused variable 'rgt' [-Wunused-variable]
  249 |         ll rgt=R[i];
      |            ^~~
meetings.cpp: In function 'll eval(node*, ll)':
meetings.cpp:69:1: warning: control reaches end of non-void function [-Wreturn-type]
   69 | }
      | ^

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