제출 #1247076

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

teams

/**

                                    * بسم الله الرحمن الرحيم *

                ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿

*/

/// author : "ASGA"


#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>


using namespace std;
using ll=long long;


struct sgt{
    vector<vector<int>>s;
    int lg,sz;
    void init(const vector<int>&a){
        int n=a.size();
        lg=__lg(n)+1;sz=1<<lg;
        s.resize(sz*2);
        for(int i=lg;i>=0;i--){
            for(int j=0;j<(1<<i);j++){
                int k=(1<<i)+j;
                if(i==lg){
                    if(j<n)s[k].push_back(a[j]);
                }
                else{
                    int l=0,r=0;
                    while(l<s[k*2].size()&&r<s[k*2+1].size()){
                        if(s[k*2][l]<s[k*2+1][r]){
                            s[k].push_back(s[k*2][l++]);
                        }
                        else{
                            s[k].push_back(s[k*2+1][r++]);
                        }
                    }
                    while(l<s[k*2].size())s[k].push_back(s[k*2][l++]);
                    while(r<s[k*2+1].size())s[k].push_back(s[k*2+1][r++]);
                }
            }
        }
    }

    vector<int>id;
    void get(int L,int R,int l,int r,int i){
        if(l>R||L>r)return;
        if(L<=l&&r<=R)id.push_back(i);
        else{get(L,R,l,(l+r)/2,i*2);get(L,R,(l+r)/2+1,r,i*2+1);}
    }
    int get(int l,int v,int st){
        id.clear();
        get(1,++l,1,sz,1);

        int ret=0;
        for(int&i:id){
            if(st)ret+=s[i].end()-lower_bound(s[i].begin(),s[i].end(),v);
            else ret+=upper_bound(s[i].begin(),s[i].end(),v)-s[i].begin();
        }

        return ret;
    }
};

int n;
vector<int>a;


sgt s;

void init(int N,int A[],int B[]){
    n=N;
    vector<array<int,2>>r;
    for(int i=0;i<n;i++)r.push_back({A[i],B[i]});
    sort(r.begin(),r.end());

    a.clear();s.s.clear();

    vector<int>b;
    for(auto&[i,j]:r)a.push_back(i);
    for(auto&[i,j]:r)b.push_back(j);
    s.init(b);
}

int can(int m,int k[]){
    sort(k,k+m);

    int x=0,y=0,c=0;

    for(int i=0;i<m;i++){
        int l=upper_bound(a.begin(),a.end(),k[i])-a.begin();
        if(l==0)return 0;
        l--;

        int tot=0;
        tot+=s.get(l,k[i],1);
        if(x>=k[i]){
            tot-=s.get(y,x,0)-c;
            tot+=s.get(y,k[i]-1,0);
        }

        if(tot<k[i])return 0;

        {
            int li=max(x,k[i]),ri=n,vv=s.get(l,k[i]-1,0);
            if(x>=k[i]){
                vv+=s.get(y,x,0)-c;
                vv-=s.get(y,k[i]-1,0);
            }
            while(li<=ri){
                int md=(li+ri)/2;
                if(s.get(l,md,0)-vv>=k[i])ri=md-1;
                else li=md+1;
            }
            ri++;

            int vl=s.get(l,ri,0)-vv;
            assert(vl>=k[i]);
            c=vl-k[i];x=ri;y=l;
        }

    }

    return 1;
}

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