Submission #1099132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099132		alexander_707070	Scales (IOI15_scales)	C++14	Compilation error	0 ms	0 KiB

scales

#include<bits/stdc++.h>
#include "teams.h"
 
#define MAXN 1000007
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*60];
    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)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;
        }
 
        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];
                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

*/

Compilation message (stderr)

scales.cpp:2:10: fatal error: teams.h: No such file or directory
    2 | #include "teams.h"
      |          ^~~~~~~~~
compilation terminated.