제출 #1191533

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

teams

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

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

//static FILE *_inputFile, *_outputFile;
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 maxi;
int num;
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(num==135)
        {
            int cnt=0;
            for(int j=0;j<t[i].size();j++)
                if(t[i][j]>=qid)cnt++;
            return cnt;
        }*/
        int id=t[i].size();
        maxi=max(maxi,i);
        int l1=0,r1=t[i].size()-1;
        while(l1<=r1)
        {
            int m1=(l1+r1)/2;
            /*if(m1>t[i].size())
            {
                //fprintf(_outputFile, "%d ", m1);
                //return 0;
            }*/
            if(t[i][m1]>=qid)
            {
                id=m1;
                r1=m1-1;
            }
            else l1=m1+1;
        }
        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);
}
int a[500001],b[500001];
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]);
        a[i]=A[i],b[i]=B[i];
    }
    trans(1,1,n);
    //fprlong longf(_outputFile,"%d ", t.query(0,1,maxn,1,3,3,5));
}

long long dp[500005];
long long dp1[500005];
int qquery(int i,int l,int r,int ql,int qr,int qid)
{
    int cnt=0;
    for(int j=0; j<n; j++)
        if(ql<=a[j]&&a[j]<=qr&&b[j]>=qid)cnt++;
    return cnt;
}
int can(int M, int k[])
{
    num++;
    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];
        //if(num==135&&i)fprintf(_outputFile, "%d \n", dp[i-1]);
        //fprlong longf(_outputFile,"%d ", v1);
        if(s.size()==0/*||dp[s.top().first]>=v1*/)
        {
            //if(num==135)fprintf(_outputFile, "%d \n", -1);
            dp[i]=v1;
            s.push({i,M});
            answer=min(answer,dp[i]);
            continue;
        }

        long long j=s.top().first;
        dp[i]=min(v1,dp[j]+query(1,1,n,k[j]+1,k[i],k[i])-k[i]);
        answer=min(answer,dp[i]);

        while(1)
        {
            if(s.size()==0)
            {
                s.push({i,M});
                break;
            }

            long long ans=M;
            j=s.top().first;
            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;
            }
            if(ans>s.top().second)s.pop();
            else
            {
                s.push({i,ans});
                //if(num==135)fprintf(_outputFile,"%d \n", ans);
                break;
            }
        }
    }

    /*if(num==135)
        for(int i=0; i<M; i++)
        {
            dp1[i]=query(1,1,n,1,k[i],k[i])-k[i];
            for(int j=0; j<i; j++)
            {
                dp1[i]=min(dp1[i],dp1[j]+query(1,1,n,k[j]+1,k[i],k[i])-k[i]);
                fprintf(_outputFile,"%d ", dp1[j]+query(1,1,n,k[j]+1,k[i],k[i])-k[i]);
            }
            fprintf(_outputFile,"%d\n",dp1[i]);
        }

    /*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;
}*/

/*
21 1 3 4 4 6 10 10 10 30 40 90 546 819 2460 3280 4100 5740 14762 22143 29524 44286 44286
21 1 3 7 8 20 30 40 90 91 91 91 273 455 819 820 1640 2460 4920 4920 29524 66429 66429
21 5 6 8 30 30 60 80 91 182 364 364 546 820 820 820 2460 3280 7380 14762 36905 36905 36905
19 4 5 8 40 50 80 182 637 637 820 3280 4920 6560 7381 7381 7381 22143 36905 66429 66429
22 1 4 6 9 10 10 10 30 40 90 91 364 546 728 820 1640 3280 7380 14762 14762 36905 44286 44286
22 1 4 5 7 10 10 10 30 50 90 91 364 546 819 820 3280 4920 5740 7381 36905 44286 51667 51667
19 3 4 8 60 90 273 273 455 455 820 820 820 2460 3280 7380 14762 29524 36905 66429 66429
18 2 6 8 20 30 40 90 455 637 637 5740 7380 7381 7381 7381 22143 36905 66429 66429
20 2 4 6 8 40 60 70 455 728 820 820 2460 4920 6560 7381 7381 7381 22143 29524 66429 66429
20 1 1 1 3 5 9 10 50 50 80 91 455 819 1640 1640 4100 4100 36905 44286 59048 59048
19 2 4 8 40 50 70 273 364 364 455 3280 4920 5740 7381 7381 7381 22143 36905 66429 66429
21 2 6 9 10 10 10 30 40 90 182 546 819 820 820 2460 2460 3280 5740 36905 36905 36905 36905
17 1 7 9 10 10 10 30 40 90 455 546 637 4920 5740 22143 44286 44286 44286
*/

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