제출 #1191486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191486		simona1230	팀들 (IOI15_teams)	C++20	0 / 100	905 ms	120188 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=5*1e5+5;

static FILE *_inputFile, *_outputFile;
int n;
vector<int> v[4*maxn];
void update(int i,int l,int r,int id,int vl)
{
    if(l==r)
    {
        v[i].push_back(vl);
        return;
    }

    int 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 build(int i,int l,int r)
{
    if(l==r)
    {
        sort(v[i].begin(),v[i].end());
        return;
    }

    int m=(l+r)/2;
    build(i*2,l,m);
    build(i*2+1,m+1,r);

    int i1=0,i2=0;
    while(i1<v[i*2].size()&&i2<v[i*2+1].size())
    {
        if(v[i*2][i1]<v[i*2+1][i2])v[i].push_back(v[i*2][i1++]);
        else v[i].push_back(v[i*2+1][i2++]);
    }

    while(i1<v[i*2].size())
        v[i].push_back(v[i*2][i1++]);

    while(i2<v[i*2+1].size())
        v[i].push_back(v[i*2+1][i2++]);
}

void init(int N, int A[], int B[])
{
    n=N;
    for(int i=0;i<n;i++)
        update(1,1,n,A[i],B[i]);

    build(1,1,n);
}

int query(int i,int l,int r,int ql,int qr,int id)
{
    if(ql>qr)return 0;
    if(ql<=l&&r<=qr)
    {
        int cid=v[i].size();
        int lf=0,rt=v[i].size()-1;

        while(lf<=rt)
        {
            int m=(lf+rt)/2;
            if(v[i][m]>=id)
            {
                cid=m;
                rt=m-1;
            }
            else lf=m+1;
        }

        return v[i].size()-cid;
    }

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

int dp[maxn];
int can(int m, int k[])
{
    sort(k,k+m);
    stack<pair<int,int> > s;
    s.push({-1,m});
    int minn=0;
    for(int i=0;i<m;i++)
    {
        while(s.size()&&s.top().second==i)s.pop();

        int p=0,pv=0;
        if(s.top().first!=-1)
        {
            p=k[s.top().first];
            pv=dp[p];
        }

        if(s.top().first==-1)dp[i]=query(1,1,n,1,k[i],k[i])-k[i];
        else dp[i]=pv+query(1,1,n,p+1,k[i],k[i])-k[i];

        int id=m;
        int l=i+1,r=m-1;
        while(l<=r)
        {
            int md=(l+r)/2;
            if(pv+query(1,1,n,p+1,k[md],k[md])<=dp[i]+query(1,1,n,k[i]+1,k[md],k[md]))
            {
                id=md;
                r=md-1;
            }
            else l=md+1;
        }

        minn=min(minn,dp[i]);
        s.push({i,id});

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

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