제출 #1191182

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191182		simona1230	Teams (IOI15_teams)	C++20	77 / 100	3949 ms	589824 KiB

teams

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

const int maxn=5*1e5+5;
multiset<int> h[4*maxn];
vector<int> t[4*maxn];
int n;

void update(int i,int l,int r,int id,int vl)
{
    h[i].insert(vl);
    if(l==r)
        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 trans(int i,int l,int r)
{
    for(auto it=h[i].begin();it!=h[i].end();it++)
        t[i].push_back(*it);
    if(l==r)return;
    int m=(l+r)/2;
    trans(i*2,l,m);
    trans(i*2+1,m+1,r);
}

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

    int 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(int i=0;i<N;i++)
        update(1,1,n,A[i],B[i]);
    trans(1,1,n);
    //fprintf(_outputFile,"%d ", t.query(0,1,maxn,1,3,3,5));
}

int dp[500001];
int can(int M, int k[])
{
    sort(k,k+M);
    int answer=0;
    stack<pair<int,int> > s;
    for(int i=0;i<M;i++)
    {
        while(s.size()&&s.top().second==i)s.pop();
        int v1=query(1,1,n,1,k[i],k[i])-k[i];
        //fprintf(_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;
        }

        int 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;
        }
        int ans=M;
        int l=i+1,r=M-1;
        while(l<=r)
        {
            int 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(int i=0;i<M;i++)
    {
        fprintf(_outputFile,"%d ", dp[i]);
    }*/

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

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