Submission #745668

#	Time	Username	Problem	Language	Result	Execution time	Memory
745668		ogibogi2004	Teams (IOI15_teams)	C++14	13 / 100	1059 ms	358684 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=5e5+6;
int n;
int a[MAXN];
int b[MAXN];
struct node
{
    int val;
    node *l, *r;
    node(int x){
        val=x;
        l=nullptr;
        r=nullptr;
    }
    node(node *_l,node *_r)
    {
        l=_l;
        r=_r;
        val=0;
        if(l)val+=l->val;
        if(r)val+=r->val;
    }
    node(node *t)
    {
        val=t->val;
        l=t->l;
        r=t->r;
    }
};
node *update(node *t,int val,int pos,int l=1,int r=n)
{
    //cerr<<"update "<<l<<" "<<r<<endl;
    if(l==r)return new node(val);
    int mid=(l+r)/2;
    if(pos>mid)
    {
        if(t==nullptr)return new node(nullptr, update(nullptr,val,pos, mid+1,r));
        else return new node(t->l, update(t->r,val,pos, mid+1,r));
    }
    else
    {
        if(t==nullptr)return new node(update(nullptr,val,pos,l,mid), nullptr);
        else return new node(update(t->l,val,pos,l,mid), t->r);
    }
}
int query(node *t,int ql,int qr,int l=1,int r=n)
{
    //cerr<<"query "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl;
    if(ql>r)return 0;
    if(t==nullptr)return 0;
    if(qr<l)return 0;
    if(l>=ql&&r<=qr)return t->val;
    int mid=(l+r)/2;
    return query(t->l,ql,qr,l,mid)+query(t->r,ql,qr,mid+1,r);
}
node *roots[MAXN];
struct segment
{
    int l,r;
};
vector<segment>v;
bool cmp(segment s1,segment s2)
{
    if(s1.r!=s2.r)return s1.r<s2.r;
    else return s1.l<s2.l;
}
vector<segment>s1[MAXN];
int sum[MAXN];
void init(int N, int A[], int B[]) {
    n=N;
    for(int i=0;i<N;i++)
    {
        a[i]=A[i];
        b[i]=B[i];
        v.push_back({A[i],B[i]});
    }
    sort(v.rbegin(),v.rend(),cmp);
    for(auto xd:v)
    {
        s1[xd.r].push_back(xd);
    }
    roots[n+1]=nullptr;
    for(int i=n;i>=1;i--)
    {
        roots[i]=roots[i+1];
        //cout<<"???\n";
        {
            for(auto xd:s1[i])
            {
                ++sum[xd.l];
                roots[i]=update(roots[i],sum[xd.l],xd.l,1,n);
                //cerr<<" "<<xd.l<<" ^^"<<endl;
            }
        }
    }
}
int m;
int k[MAXN];
int dp[MAXN];
int get_value1(int x)
{
    node* root_we_need = roots[x];
    return query(root_we_need,1,x,1,n);
}
int get_value(int i1,int i2)
{
    //should return no. of segments with k[i2]>=l>k[i1] and r>=k[i2]
    //persistent segment tree can do :(
    node *root_we_need = roots[k[i2]];
    return query(root_we_need, k[i1]+1,k[i2],1,n);
}
int can(int M, int K[]) {
    //cerr<<"========query=========";
    sort(K,K+M);
    int sumk=0;
    for(int i=0;i<M;i++)
    {
        k[i]=K[i];
        sumk+=k[i];
    }
    if(sumk>n)return 0;
    m=M;
    dp[0]=get_value1(K[0])-K[0];
    if(dp[0]<0)return 0;
    vector<int>ids;
    ids.push_back(0);
    //cerr<<"0 : "<<dp[0]<<endl;
    for(int i=1;i<m;i++)
    {
        while(ids.size()>1)
        {
            int id1=ids[ids.size()-2];
            int id2=ids[ids.size()-1];
            if(get_value(id1, i)+dp[id1]<=get_value(id2, i)+dp[id2])
            {
                ids.pop_back();
            }
            else
            {
                break;
            }
        }
        dp[i]=dp[ids.back()]+get_value(ids.back(), i)-K[i];
        //cerr<<i<<" : "<<dp[i]<<endl;
        if(dp[i]<0)return 0;
        ids.push_back(i);
    }
    return 1;
}

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