Submission #1147761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147761		alexdd	Teams (IOI15_teams)	C++20	100 / 100	2062 ms	122852 KiB

teams

#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
int n;
pair<int,int> v[500005];
vector<int> aint[1100005],ofa[500005];
void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        aint[nod] = ofa[st];
        sort(aint[nod].begin(),aint[nod].end());
        return;
    }
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);

    aint[nod] = aint[nod*2];
    for(int x:aint[nod*2+1]) aint[nod].push_back(x);

    sort(aint[nod].begin(), aint[nod].end());
}
int qry(int nod, int st, int dr, int qle, int qri)
{
    if(st==dr)
    {
        return (int)aint[nod].size() - (lower_bound(aint[nod].begin(), aint[nod].end(), qri) - aint[nod].begin());
    }
    int mij=(st+dr)/2;
    if(qle<=mij) return qry(nod*2,st,mij,qle,qri);
    else
    {
        return qry(nod*2+1,mij+1,dr,qle,qri) + (int)aint[nod*2].size() - (lower_bound(aint[nod*2].begin(), aint[nod*2].end(), qri) - aint[nod*2].begin());
    }
}
void init(int32_t N, int32_t A[], int32_t B[])
{
    n=N;
    for(int i=0;i<N;i++)
    {
        v[i] = {A[i],B[i]};
        ofa[v[i].first].push_back(v[i].second);
    }
    build(1,1,n);
}

int numara(int le, int ri)
{
    return qry(1,1,n,le,ri);
    int cv=0;
    for(int i=0;i<n;i++)
        if(v[i].first <= le && v[i].second >= ri)
            cv++;
    return cv;
}

const int MAXV = 1000;
int inc[MAXV+5][MAXV+5],cate[MAXV+5][MAXV+5];
int32_t can(int32_t M, int32_t K[])
{
    long long tot=0;
    for(int i=0;i<M;i++)
        tot += K[i];
    if(tot > n)
        return 0;

    sort(K,K+M);
    vector<pair<int,int>> aux;
    for(int i=0;i<M;i++)
    {
        if(!aux.empty() && K[i]==aux.back().first)
            aux.back().second += K[i];
        else
            aux.push_back({K[i],K[i]});
    }
    assert((int)aux.size() <= MAXV);

    set<pair<int,int>> s;
    for(int i=0;i<aux.size();i++)
    {
        for(int j=i;j<aux.size();j++)
        {
            if(j>i && inc[i][j-1]==0)
                inc[i][j]=0;
            else
                inc[i][j] = numara(aux[i].first, aux[j].first);
        }
        for(int j=i;j<aux.size();j++)
        {
            cate[i][j] = inc[i][j];
            if(i>0) cate[i][j] -= inc[i-1][j];
            if(j+1<aux.size()) cate[i][j] -= inc[i][j+1];
            if(i>0 && j+1<aux.size()) cate[i][j] += inc[i-1][j+1];
        }

        while(!s.empty() && (*s.begin()).first < i)
            s.erase(s.begin());

        for(int j=i;j<aux.size();j++)
            if(cate[i][j]>0)
            {
                auto it = s.lower_bound({j,-1});
                pair<int,int> x = *it;
                if(it!=s.end() && x.first==j)
                {
                    s.erase(it);
                    s.insert({x.first, x.second+cate[i][j]});
                }
                else
                    s.insert({j,cate[i][j]});
            }

        int ramase = aux[i].second;
        while(ramase>0)
        {
            if(s.empty())
                return 0;
            auto it = s.begin();
            pair<int,int> x = *it;
            assert(x.first >= i);
            int d = min(ramase, x.second);
            ramase -= d;
            x.second -= d;
            if(x.second > 0)
            {
                s.erase(it);
                s.insert(x);
                break;
            }
            else
            {
                s.erase(it);
            }
        }
    }
    return 1;
}

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