제출 #1105569

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1105569		alexander707070	팀들 (IOI15_teams)	C++14	77 / 100	3635 ms	145628 KiB

teams

#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include "teams.h"
 
#define MAXN 500007
using namespace std;
 
int n,m;
pair<int,int> p[MAXN];
int k[MAXN];
 
struct interval{
    int l,r,k,e;
 
    int len(){
        return r-l+1;
    }
};
 
interval combine(interval a,interval b){
    interval c={a.l,b.r,0,0};
 
    if(a.k>a.len())swap(a,b);
 
    if(a.k>a.len() and b.k>b.len()){
        c.k=c.len()+1;
        c.e=0;
    }else if(b.k>b.len()){
        c.k=a.k+b.len();
        c.e=a.e;
    }else{
        if(a.e>b.e)swap(a,b);
 
        c.e=a.e;
        c.k=a.k+b.k-1;
    }
 
    return c;
}
 
struct PST{
    struct node{
        int l,r,sum;
    };
 
    node tree[MAXN*30];
    int root[MAXN],num,last;
 
    void upgrade(){
        last++; root[last]=num;
    }
 
    void addnode(int l,int r){
        num++;
        tree[num].l=l; tree[num].r=r;
    }
 
    int update(int v,int l,int r,int pos){
        if(l==r){
            addnode(0,0);
 
            tree[num].sum=tree[v].sum+1;
            return num;
        }else{
            int tt=(l+r)/2;
            int lt=tree[v].l,rt=tree[v].r;
 
            if(pos<=tt){
                lt=update(tree[v].l,l,tt,pos);
            }else{
                rt=update(tree[v].r,tt+1,r,pos);
            }
 
            addnode(lt,rt);
            tree[num].sum=tree[lt].sum+tree[rt].sum;
            return num;
        }
    }
 
    int getkth(int v1,int v2,int l,int r,int k){
        if(l==r)return l;
 
        int tt=(l+r)/2;
        if(tree[tree[v2].l].sum-tree[tree[v1].l].sum>=k)return getkth(tree[v1].l,tree[v2].l,l,tt,k);
        return getkth(tree[v1].r,tree[v2].r,tt+1,r,k-(tree[tree[v2].l].sum-tree[tree[v1].l].sum));
    }
 
    void upd(int x){
        update(root[last],1,n,x);
        upgrade();
    }
 
    int kth(int l,int r,int k){
        return getkth(root[l-1],root[r],1,n,k);
    }
 
    int smallest(int l,int r,int val){
        int from=0,to=r-l+2,tt;
 
        while(from+1<to){
            tt=(from+to)/2;
            if(kth(l,r,tt)>=val){
                to=tt;
            }else{
                from=tt;
            }
        }
 
        return to;
    }
}seg;
 
 
void init(int N, int A[], int B[]) {
//void init(int N, vector<int> A, vector<int> B) {
    n=N;
    for(int i=1;i<=n;i++){
        p[i]={A[i-1],B[i-1]};
    }
    sort(p+1,p+n+1);
 
    for(int i=1;i<=n;i++)seg.upd(p[i].second);
}
 
int findpos(int from,int val){
    int l=from,r=n+1,tt;
    while(l+1<r){
        tt=(l+r)/2;
        if(p[tt].first<=val){
            l=tt;
        }else{
            r=tt;
        }
    }
 
    return l;
}
 
int can(int M,int K[]) {
//int can(int M,vector<int> K) {
    m=M;
    for(int i=1;i<=m;i++){
        k[i]=K[i-1];
    }
    sort(k+1,k+m+1);
 
    vector<interval> w;
 
    int pt=0;
    for(int i=1;i<=m;i++){
        int nxt=findpos(pt,k[i]);
 
        if(nxt>pt){
            w.push_back({pt+1,nxt,1,seg.kth(pt+1,nxt,1)});
            pt=nxt;
        }
    
        for(int f=int(w.size())-1;f>=0;f--){
            int s=seg.smallest(w[f].l,w[f].r,k[i]);
            if(s<=w[f].k)continue;
 
            w[f].k=s;
            if(s<=w[f].len())w[f].e=seg.kth(w[f].l,w[f].r,s);
            else w[f].e=0;
        }
 
        vector<interval> news={w[0]};
        
        for(int f=1;f<w.size();f++){
            news.push_back(w[f]);
            while(news.size()>1 and news[news.size()-2].e<=news[news.size()-1].e){
                news[news.size()-2]=combine(news[news.size()-2],news[news.size()-1]);
                news.pop_back();
            }
        }
 
        w=news;
 
        if(w.empty())return 0;
 
        while(k[i]>0){
 
            if(w.size()==1){
                if(w[0].k+k[i]-1>w[0].len())return 0;
                w[0].k+=k[i];
 
                if(w[0].k<=w[0].len())w[0].e=seg.kth(w[0].l,w[0].r,w[0].k);
                else w[0].e=0;
 
                break;
            }
 
            interval s=w.back();
            for(int z=20;z>=0;z--){
                if((1<<z)>s.len()-s.k+1 or (1<<z)>k[i])continue;
 
                int curr=seg.kth(s.l,s.r,s.k+(1<<z)-1);
                if(curr<w[w.size()-2].e){
                    k[i]-=(1<<z);
                    s.k+=(1<<z);
                }
            }
            
            if(s.k<=s.len())s.e=seg.kth(s.l,s.r,s.k);
            else s.e=0;
 
            w[w.size()-1]=s;
 
            if(k[i]>0){
                w[w.size()-2]=combine(w[w.size()-2],w[w.size()-1]);
                w.pop_back();
            }
        }
    }
 
	return 1;
}
 
/*int main(){
 
    init(5,{4,3,2,2,1},{4,5,3,5,4});
    cout<<can(2,{1,2})<<"\n";
 
	return 0;
}*/
 
/*
 
4 4
3 5
2 3
2 5
1 4
 
5
 
*/

컴파일 시 표준 에러 (stderr) 메시지

teams.cpp: In member function 'int PST::getkth(int, int, int, int, int)':
teams.cpp:82:46: warning: declaration of 'k' shadows a global declaration [-Wshadow]
   82 |     int getkth(int v1,int v2,int l,int r,int k){
      |                                          ~~~~^
teams.cpp:12:5: note: shadowed declaration is here
   12 | int k[MAXN];
      |     ^
teams.cpp: In member function 'int PST::kth(int, int, int)':
teams.cpp:95:29: warning: declaration of 'k' shadows a global declaration [-Wshadow]
   95 |     int kth(int l,int r,int k){
      |                         ~~~~^
teams.cpp:12:5: note: shadowed declaration is here
   12 | int k[MAXN];
      |     ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:171:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<interval>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |         for(int f=1;f<w.size();f++){
      |                     ~^~~~~~~~~

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