Submission #1191186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191186		simona1230	Teams (IOI15_teams)	C++20	77 / 100	928 ms	173416 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;

const long long maxn=6*1e5+5;
vector<long long> t[4*maxn];
long long n;

void update(long long i,long long l,long long r,long long id,long long vl)
{
    if(l==r)
    {
        t[i].push_back(vl);
        return;
    }

    long long m=(l+r)/2;
    if(id<=m)update(i*2,l,m,id,vl);
    else update(i*2+1,m+1,r,id,vl);
}

void trans(long long i,long long l,long long r)
{
    if(l==r)
    {
        sort(t[i].begin(),t[i].end());
        return;
    }
    long long m=(l+r)/2;
    trans(i*2,l,m);
    trans(i*2+1,m+1,r);
    long long i1=0,i2=0;
    while(i1<t[i*2].size()||i2<t[i*2+1].size())
    {
        if(i1==t[i*2].size())t[i].push_back(t[i*2+1][i2++]);
        else if(i2==t[i*2+1].size()||t[i*2][i1]<t[i*2+1][i2])t[i].push_back(t[i*2][i1++]);
        else t[i].push_back(t[i*2+1][i2++]);
    }
}

long long query(long long i,long long l,long long r,long long ql,long long qr,long long qid)
{
    //cout<<l<<" - "<<r<<endl;
    if(ql>qr)return 0;
    if(ql<=l&&r<=qr)
    {
        if(t[i].size()==0)return 0;
        if(t[i][0]>=qid)return t[i].size();
        if(t[i][t[i].size()-1]<qid)return 0;
        long long id=t[i].size();
        long long lf=0,rt=t[i].size()-1;
        while(lf<=rt)
        {
            long long m=(lf+rt)/2;
            //cout<<"? "<<m<<" "<<lf<<" "<<rt<<endl;
            if(m>=t[i].size())
            {
                for(long long j=0;j<1e9;j++);
            }
            if(t[i][m]>=qid)
            {
                rt=m-1;
                id=m;
            }
            else lf=m+1;
        }
        /*for(long long j=0;j<t[i].size();j++)
            cout<<t[i][j]<<" ";
        cout<<endl;
        cout<<id<<" "<<qid<<" +"<<endl;*/
        return t[i].size()-id;
    }

    long long m=(l+r)/2;
    return query(i*2,l,m,ql,min(qr,m),qid)+query(i*2+1,m+1,r,max(m+1,ql),qr,qid);
}

void init(int N, int A[], int B[])
{
    n=N;
    for(long long i=0;i<N;i++)
        update(1,1,n,A[i],B[i]);
    trans(1,1,n);
    //fprlong longf(_outputFile,"%d ", t.query(0,1,maxn,1,3,3,5));
}

long long dp[500005];
int can(int M, int k[])
{
    sort(k,k+M);
    long long answer=0;
    stack<pair<long long,long long> > s;
    for(long long i=0;i<M;i++)
    {
        while(s.size()&&s.top().second==i)s.pop();
        long long v1=query(1,1,n,1,k[i],k[i])-k[i];
        //fprlong longf(_outputFile,"%d ", v1);
        if(s.size()==0/*||dp[s.top().first]>=v1*/)
        {
            dp[i]=v1;
            s.push({i,M});
            answer=min(answer,dp[i]);
            continue;
        }

        long long j=s.top().first;
        dp[i]=dp[j]+query(1,1,n,k[j]+1,k[i],k[i])-k[i];
        if(dp[i]>v1)
        {
            dp[i]=v1;
            while(s.size())s.pop();
            s.push({i,M});
            answer=min(answer,dp[i]);
            continue;
        }
        long long ans=M;
        long long l=i+1,r=M-1;
        while(l<=r)
        {
            long long m=(l+r)/2;
            if(dp[i]+query(1,1,n,k[i]+1,k[m],k[m])>=dp[j]+query(1,1,n,k[j]+1,k[m],k[m]))
            {
                ans=m;
                r=m-1;
            }
            else l=m+1;
        }
        answer=min(answer,dp[i]);

        s.push({i,ans});
    }

    /*for(long long i=0;i<M;i++)
    {
        fprlong longf(_outputFile,"%d ", dp[i]);
    }*/

    if(answer<0)return 0;
    return 1;
}

/*long long main()
{
    cin>>n;
    for(long long i=1;i<=n;i++)
    {
        long long x,y;
        cin>>x>>y;
        update(1,1,10,x,y);
    }

    trans(1,1,10);
    cout<<"done"<<endl;
    long long q;
    cin>>q;
    for(long long i=1;i<=q;i++)
    {
        long long x,y,xx,yy;
        cin>>x>>y>>xx>>yy;
        cout<<query(1,1,10,x,y,xx)<<endl;
    }
    return 0;
}*/

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