Submission #1067883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067883		Muhammad_Aneeq	Meetings (IOI18_meetings)	C++17	19 / 100	73 ms	3024 KiB

meetings

#include <vector>
using namespace std;
int const N=1e5+10;
struct node
{
    int msb=0,mp=0,ms=0;
    bool valid=0;
};
node St[4*N]={};
node comb(node a,node b)
{
    node c;
    c.valid=(a.valid&&b.valid);
    c.msb=max(a.msb,b.msb);
    if (a.ms&&b.mp)
        c.msb=max(c.msb,a.ms+b.mp);
    c.ms=b.ms;
    if (a.valid&&b.valid)
        c.ms=(a.ms+b.ms);
    c.mp=a.mp;
    if (b.valid&&a.valid)
        c.mp=max(c.mp,a.mp+b.mp);
    return c;
}
void update(int i,int r,int st,int en,int val)
{
    if (st==en)
    {
        if (val==1)
        {
            St[i].msb=St[i].ms=St[i].mp=St[i].valid=1;
        }
        return;
    }
    int mid=(st+en)/2;
    if (r<=mid)
        update(i*2,r,st,mid,val);
    else
        update(i*2+1,r,mid+1,en,val);
    St[i]=comb(St[i*2],St[i*2+1]);
}
node get(int i,int st,int en,int l,int r)
{
    if (st>=l&&en<=r)
        return St[i];
    if (st>r||en<l)
    {
        node c;
        c.valid=1;
        return c;
    }
    int mid=(st+en)/2;
    return comb(get(i*2,st,mid,l,r),get(i*2+1,mid+1,en,l,r));
}
vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R)
{
    int n=H.size();
    vector<long long>ans(L.size(),1e15);
    bool subt3=1;
    for (int i=0;i<n;i++)
        if (H[i]>2)
            subt3=0;
    if (subt3)
    { 
        for (int i=0;i<n;i++)
            update(1,i,0,n-1,H[i]);
        vector<long long>ans;
        for (int i=0;i<L.size();i++)
        {
            node z=get(1,0,n-1,L[i],R[i]);
            ans.push_back(2*(R[i]-L[i]+1)-z.msb);
        }
        return ans;
    }
    int val[n]={};
    long long pre[n+1]={};
    for (int i=0;i<n;i++)
    {
        int mx=H[i];
        val[i]=mx;
        for (int j=i-1;j>=0;j--)
        {
            mx=max(mx,H[j]);
            val[j]=mx;
        }
        mx=H[i];
        for (int j=i+1;j<n;j++)
        {
            mx=max(mx,H[j]);
            val[j]=mx;
        }
        for (int j=1;j<=n;j++)
            pre[j]=pre[j-1]+val[j-1];
        for (int j=0;j<L.size();j++)
        {
            if (i>=L[j]&&i<=R[j])
                ans[j]=min(ans[j],pre[R[j]+1]-pre[L[j]]);
        }
    }
    return ans;
}

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:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (int i=0;i<L.size();i++)
      |                      ~^~~~~~~~~
meetings.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for (int j=0;j<L.size();j++)
      |                      ~^~~~~~~~~

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