Submission #1191773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191773		vivkostov	Teams (IOI15_teams)	C++20	77 / 100	4093 ms	66492 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"
struct cell
{
    int l,r;
};
struct seg
{
    int l,r,st;
};
struct pro
{
    int pos,st;
};
bool cmp(cell a1,cell a2)
{
    return a1.l<a2.l;
}
cell c[500005];
seg p[5000005];
pro a[500005];
int n,m,d[500005],num,dp[500005];
int br;
void check(int h)
{
    if(!p[h].l)
    {
        p[h].l=br;
        br++;
        p[h].r=br;
        br++;
    }
}
void build(int l,int r,int h)
{
    if(l==r)return;
    int mid=(l+r)/2;
    check(h);
    build(l,mid,p[h].l);
    build(mid+1,r,p[h].r);
}
void calc(int h)
{
    p[h].st=p[p[h].l].st+p[p[h].r].st;
}
void update(int l,int r,int q,int h,int last)
{
    if(l==r)
    {
        if(!p[h].st)p[h].st+=p[last].st;
        p[h].st++;
        return;
    }
    int mid=(l+r)/2;
    if(mid>=q)
    {
        if(!p[h].l)
        {
            p[h].l=br;
            br++;
        }
        update(l,mid,q,p[h].l,p[last].l);
    }
    else
    {
        if(!p[h].r)
        {
            p[h].r=br;
            br++;
        }
        update(mid+1,r,q,p[h].r,p[last].r);
    }
    calc(h);
}
void fil(int l,int r,int h,int last)
{
    if(l==r)return;
    int mid=(l+r)/2;
    if(!p[h].l)p[h].l=p[last].l;
    else fil(l,mid,p[h].l,p[last].l);
    if(!p[h].r)p[h].r=p[last].r;
    else fil(mid+1,r,p[h].r,p[last].r);
    calc(h);
}
int query(int l,int r,int ql,int qr,int h)
{
    if(l>qr||r<ql)return 0;
    if(l>=ql&&r<=qr)return p[h].st;
    int mid=(l+r)/2;
    return query(l,mid,ql,qr,p[h].l)+query(mid+1,r,ql,qr,p[h].r);
}
void init(int N,int a[],int b[])
{
    n=N;
    br=n+1;
    for(int i=1;i<=n;i++)
    {
        c[i].l=a[i-1];
        c[i].r=b[i-1];
    }
    std::sort(c+1,c+n+1,cmp);
    build(1,n,1);
    int to=1;
    for(int i=1;i<=n;i++)
    {
        while(c[to].l==i)
        {
            update(1,n,c[to].r,i,i-1);
            to++;
        }
        if(i!=1)fil(1,n,i,i-1);
    }
    return;
}
bool check()
{
    int nn=0;
    for(int i=1;i<=m;i++)
    {
        nn+=d[i];
    }
    if(nn>n)return false;
    return true;
}
void merg()
{
    std::sort(d+1,d+m+1);
    for(int i=1;i<=m;i++)
    {
        if(a[num].pos!=d[i])
        {
            num++;
            a[num].pos=d[i];
            a[num].st+=d[i];
        }
        else
        {
            a[num].st+=d[i];
        }
    }
}
bool make_dp()
{
    int opt,base;
    for(int i=1;i<=num;i++)
    {
        dp[i]=1e9;
        opt=query(1,n,a[i].pos,n,a[i].pos);
        base=1e9;
        for(int j=i-1;j>=0;j--)
        {
            if(dp[j]<base)
            {
                base=dp[j];
                dp[i]=std::min(dp[i],dp[j]+opt-query(1,n,a[i].pos,n,a[j].pos)-a[i].st);
            }
        }
        //cout<<a[i].st<<" "<<query(1,n,i,n,i)<<" "<<query(1,n,i,n,0)<<endl;
        //cout<<dp[i]<<endl;
        if(dp[i]<0)return false;
    }
    return true;
}
void clea()
{
    for(int i=1;i<=m;i++)
    {
        d[i]=0;
        dp[i]=0;
        a[i].pos=0;
        a[i].st=0;
    }
    num=0;
}
int can(int M,int D[])
{
    m=M;
    clea();
    for(int i=m;i>=1;i--)
    {
        d[i]=D[i-1];
    }
    d[0]=0;
    if(!check())return false;
    merg();
    return make_dp();
}

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 0 / 23