Submission #1312819

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312819		activedeltorre	Teams (IOI15_teams)	C++20	0 / 100	192 ms	24332 KiB

teams

#include "teams.h"
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
pair<int,int>vec[500005];
int n;
vector<int>aint[500005];
bool cmp(pair<int,int>a,pair<int,int>b)
{
    if(a.second==b.second)
    {
        return a.first<b.first;
    }
    return a.second<b.second;
}
void build(int node,int st,int dr)
{
    if(st==dr)
    {
        aint[node].push_back(vec[st].first);
        return;
    }
    int mij=(st+dr)/2;
    build(node*2,st,mij);
    build(node*2+1,mij+1,dr);
    for(int i=st;i<=dr;i++)
    {
        aint[node].push_back(vec[i].first);
    }
    sort(aint[node].begin(),aint[node].end());
}
int query(int node,int st,int dr,int qst,int qdr,int val)
{
    if(st>qdr || st>dr || qst>dr || qst>qdr)
    {
        return 0;
    }
    if(qst<=st && dr<=qdr)
    {
        return aint[node].size()-(lower_bound(aint[node].begin(),aint[node].end(),val)-aint[node].begin());
    }
    int mij=(st+dr)/2;
    return(query(node*2,st,mij,qst,qdr,val)+query(node*2+1,mij+1,dr,qst,qdr,val));
}
void init(int N, int A[], int B[])
{
    n=N;
    for(int i=0; i<N; i++)
    {
        vec[i+1].first=A[i];
        vec[i+1].second=B[i];
    }
    sort(vec+1,vec+n+1,cmp);
    build(1,1,n);
}
int dp[1005];
priority_queue<int>pq;
int can(int M, int K[])
{
    if(M>=1000)
    {
        int dr,index=M-1;
        sort(K,K+M);
        while(pq.size())
        {
            pq.pop();
        }
        vec[0].second=-1;
        for(int i=n; i>=0; i--)
        {
            while(vec[i].second<K[index] && index>=0)
            {
                int cnt=K[index];
                while(pq.size() && pq.top()>K[index])
                {
                    pq.pop();
                }
                while(pq.size() && K[index])
                {
                    K[index]--;
                    pq.pop();
                }
                if(K[index]!=0)
                {
                    return 0;
                }
                else
                {
                    index--;
                }
            }
            pq.push(vec[i].first);
        }
        return 1;
    }
    else
    {
        int dr,index=M-1;
        sort(K,K+M);
        for(int i=0;i<M;i++)
        {
            int vec=query(1,1,n,1,K[i],K[i]);
            dp[i]=K[i]-vec;
            for(int j=0;j<i;j++)
            {
                dp[i]=max(dp[i],dp[j]+K[i]-query(1,1,n,1,K[j],K[i]));
            }
            if(dp[i]>=1)
            {
                return 0;
            }
        }
        return 1;
    }
}

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