Submission #884039

#	Time	Username	Problem	Language	Result	Execution time	Memory
884039		andrei_boaca	Meetings (IOI18_meetings)	C++17	19 / 100	5584 ms	649272 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;
};
deque<interv> s[800005];
ll lazy[800005];
ll eval(ll me, ll poz)
{
    ll st=0;
    ll dr=s[me].size();
    dr--;
    while(st<=dr)
    {
        ll mij=(st+dr)/2;
        if(s[me][mij].st>poz)
        {
            dr=mij-1;
            continue;
        }
        if(s[me][mij].dr<poz)
        {
            st=mij+1;
            continue;
        }
        ll val=s[me][mij].a*poz+s[me][mij].b+lazy[me];
        return val;
    }
}
ll cntnodes=0;
ll plsnode()
{
    cntnodes++;
    s[cntnodes].clear();
    lazy[cntnodes]=0;
    return cntnodes;
}
ll build(ll l,ll r)
{
    ll poz=getbest(l,r);
    ll hv=v[poz];
    //node *nod = new node;
    ll nod=0;
    ll nodl=0;
    ll nodr=0;
    if(l<=poz-1)
        nodl=build(l,poz-1);
    if(r>=poz+1)
        nodr=build(poz+1,r);
    ll valmij=0;
    if(nodl==0)
    {
        valmij=v[poz];
        nodl=plsnode();
    }
    else
        valmij=eval(nodl,poz-1)+v[poz];
    s[nodl].push_back({poz,poz,0,valmij-lazy[nodl]});
    ll off=hv*(poz-l+1);
    if(nodr==0)
    {
        nod=nodl;
        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;
    lazy[nodr]+=off;
    while(!s[nodr].empty())
    {
        interv a=s[nodr].front();
        ll p=a.dr;
        ll val1=valmij+hv*p;
        ll val2=a.a*p+a.b+lazy[nodr];
        if(val1<=val2)
        {
            s[nodr].pop_front();
            continue;
        }
        else
        {
            ll st=a.st;
            ll dr=a.dr;
            ll j=st-1;
            while(st<=dr)
            {
                ll mij=(st+dr)/2;
                val1=valmij+hv*mij;
                val2=a.a*mij+a.b+lazy[nodr];
                if(val1<=val2)
                {
                    j=mij;
                    st=mij+1;
                }
                else
                    dr=mij-1;
            }
            s[nodr].pop_front();
            a.st=j+1;
            s[nodr].push_front(a);
            interv add={poz+1,j,hv,valmij-lazy[nodr]};
            if(add.st<=add.dr)
                s[nodr].push_front(add);
            break;
        }
    }
    if(s[nodr].empty())
        s[nodr].push_back({poz+1,r,hv,valmij-lazy[nodr]});
    ll rez=0;
    if(s[nodl].size()<s[nodr].size())
    {
        ll dif=lazy[nodr]-lazy[nodl];
        rez=nodr;
        while(!s[nodl].empty())
        {
            interv a=s[nodl].back();
            s[nodl].pop_back();
            a.b-=dif;
            s[rez].push_front(a);
        }
    }
    else
    {
        ll dif=lazy[nodl]-lazy[nodr];
        rez=nodl;
        while(!s[nodr].empty())
        {
            interv a=s[nodr].front();
            s[nodr].pop_front();
            a.b-=dif;
            s[rez].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);
    }
    cntnodes=0;
    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);
    }
    cntnodes=0;
    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:249:12: warning: unused variable 'lft' [-Wunused-variable]
  249 |         ll lft=L[i];
      |            ^~~
meetings.cpp:250:12: warning: unused variable 'rgt' [-Wunused-variable]
  250 |         ll rgt=R[i];
      |            ^~~
meetings.cpp: In function 'll eval(ll, ll)':
meetings.cpp:58:1: warning: control reaches end of non-void function [-Wreturn-type]
   58 | }
      | ^

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