Submission #1098995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098995		alexander_707070	Teams (IOI15_teams)	C++14	13 / 100	3322 ms	133900 KiB

teams

#include<bits/stdc++.h>
#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]);
       // cout<<k[i]<<" adding "<<pt+1<<" "<<nxt<<"\n";

        if(nxt>pt){
            w.push_back({pt+1,nxt,1,seg.kth(pt+1,nxt,1)});
            //cout<<w.back().e<<" at back\n";
            pt=nxt;
        }

        int to=w.size();
        for(int f=w.size()-1;f>=0;f--){
            int s=seg.smallest(w[f].l,w[f].r,k[i]);
            if(s<w[f].k)break;

            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;

           // cout<<"cutting to "<<w[f].k<<" "<<w[f].e<<"\n";

            to=f+1;
        }

        while(w.size()>to){
            //cout<<"compressing\n";
            w[w.size()-2]=combine(w[w.size()-2],w[w.size()-1]);
            w.pop_back();
        }

        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];
                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;
                }
            }

            if(k[i]>0 or s.k==s.len()+1){
                w[w.size()-2]=combine(w[w.size()-2],s);
                w.pop_back();
            }
        }
    }

	return 1;
}

/*int main(){

    init(4,{1,2,2,2},{2,3,3,4});
    cout<<can(2,{1,3})<<"\n";
    cout<<can(2,{1,1})<<"\n";

	return 0;
}*/

Compilation message (stderr)

teams.cpp: In member function 'int PST::getkth(int, int, int, int, int)':
teams.cpp:78:46: warning: declaration of 'k' shadows a global declaration [-Wshadow]
   78 |     int getkth(int v1,int v2,int l,int r,int k){
      |                                          ~~~~^
teams.cpp:9:5: note: shadowed declaration is here
    9 | int k[MAXN];
      |     ^
teams.cpp: In member function 'int PST::kth(int, int, int)':
teams.cpp:91:29: warning: declaration of 'k' shadows a global declaration [-Wshadow]
   91 |     int kth(int l,int r,int k){
      |                         ~~~~^
teams.cpp:9:5: note: shadowed declaration is here
    9 | int k[MAXN];
      |     ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:158:22: warning: conversion from 'std::vector<interval>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  158 |         int to=w.size();
      |                ~~~~~~^~
teams.cpp:159:27: warning: conversion from 'std::vector<interval>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  159 |         for(int f=w.size()-1;f>=0;f--){
      |                   ~~~~~~~~^~
teams.cpp:172:23: warning: comparison of integer expressions of different signedness: 'std::vector<interval>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  172 |         while(w.size()>to){
      |               ~~~~~~~~^~~

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