Submission #879620

#	Time	Username	Problem	Language	Result	Execution time	Memory
879620		andrei_boaca	Meetings (IOI18_meetings)	C++17	36 / 100	320 ms	214848 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
const ll INF=1e9;
typedef pair<ll,ll> pll;
ll n,q,v[100005],rmq[21][100005],loga[100005];
ll sdist[5005][5005];
ll getmax(ll l,ll r)
{
    ll lg=loga[r-l+1];
    return max(rmq[lg][l],rmq[lg][r-(1<<lg)+1]);
}
ll nrsecv=0;
struct date
{
    ll l,r;
} secv[100005];
set<pll> setik;
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,std::vector<int> R)
{
    n=H.size();
    vector<ll> sol;
    q=L.size();
    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;
    }
    if(n<=5000&&q<=5000)
    {
        for(int i=n;i>=1;i--)
        {
            rmq[0][i]=v[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]=max(rmq[j][i],rmq[j-1][poz]);
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                ll st=min(i,j);
                ll dr=max(i,j);
                ll val=getmax(st,dr);
                sdist[i][j]=sdist[i][j-1]+val;
            }
        }
        for(int z=0;z<q;z++)
        {
            int l=L[z]+1;
            int r=R[z]+1;
            ll ans=1e18;
            for(int i=l;i<=r;i++)
                ans=min(ans,sdist[i][r]-sdist[i][l-1]);
            sol.push_back(ans);
        }
        return sol;
    }
    for(int i=1;i<=n;i++)
        if(v[i]==1)
        {
            ll r=i;
            while(r<=n&&v[r]==1)
                r++;
            r--;
            nrsecv++;
            secv[nrsecv]={i,r};
            setik.insert({i,r});
            i=r;
        }
    for(int i=nrsecv;i>=1;i--)
    {
        rmq[0][i]=secv[i].r-secv[i].l+1;
        for(int j=1;j<=20;j++)
        {
            rmq[j][i]=rmq[j-1][i];
            int poz=i+(1<<(j-1));
            if(poz<=nrsecv)
                rmq[j][i]=max(rmq[j][i],rmq[j-1][poz]);
        }
    }
    for(int z=0;z<q;z++)
    {
        ll l=L[z]+1;
        ll r=R[z]+1;
        ll st=1;
        ll dr=nrsecv;
        ll fst=nrsecv+1;
        ll best=0;
        while(st<=dr)
        {
            ll mij=(st+dr)/2;
            if(secv[mij].l>=l)
            {
                fst=mij;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
        st=1;
        dr=nrsecv;
        ll lst=0;
        while(st<=dr)
        {
            ll mij=(st+dr)/2;
            if(secv[mij].r<=r)
            {
                lst=mij;
                st=mij+1;
            }
            else
                dr=mij-1;
        }
        if(fst<=lst)
            best=getmax(fst,lst);
        if(v[l]==1)
        {
            auto it=prev(setik.lower_bound({l,INF}));
            ll rgt=min(r,(*it).second);
            best=max(best,rgt-l+1);
        }
        if(v[r]==1)
        {
            auto it=prev(setik.lower_bound({r,INF}));
            ll lft=max(l,(*it).first);
            best=max(best,r-lft+1);
        }
        sol.push_back(2LL*(r-l+1)-best);
    }
    return sol;
}

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