Submission #91750

#	Time	Username	Problem	Language	Result	Execution time	Memory
91750		KLPP	Teams (IOI15_teams)	C++14	77 / 100	2275 ms	525312 KiB

teams

#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long int lld;
typedef pair<lld,lld> pll;
#define MAXN 1000000
#define SQ 1000000000000
#define DEBUG 0
/*
4
2 4
1 2
2 3
2 3
2
2 1 3
2 1 1

*/
struct ST
{
    ST *L,*R;
    vector<lld> v;
    lld l,r;
};
typedef ST *tree;
void ext(tree n)
{
    if(!n->L)
    {
        n->L=new ST();
        n->R=new ST();
        lld mid=(n->l+n->r)/2;
        n->L->l=n->l;
        n->L->r=mid;
        n->R->l=mid+1;
        n->R->r=n->r;
    }
}
void upd(tree n,lld pos, lld val)
{
    //cout<<n->l<<" "<<n->r<<endl;
    if(pos<n->l || n->r<pos)return;
    //cout<<n->l<<" "<<n->r<<endl;
    n->v.push_back(val);
    if(n->l==n->r)return;
    ext(n);
    upd(n->L,pos,val);
    upd(n->R,pos,val);
}
int Q(tree n,lld l, lld r, int e)
{
    if(!n)return 0;
    if(r<n->l || n->r<l)return 0;
    if(l<=n->l && n->r<=r){
        int lo,hi;
        lo=-1;
        hi=n->v.size();
        while(hi-lo>1){
            int mid=(lo+hi)/2;
            if(n->v[mid]>e)hi=mid;
            else lo=mid;
        }
        //cout<<hi<<" "<<e<<endl;
        return hi;
    }
    return Q(n->L,l,r,e)+Q(n->R,l,r,e);
}

int query(tree n,lld l, lld r, int s, int e){
    return Q(n,l,r,e)-Q(n,l,r,s-1);
}
lld nav(tree n, int s, int e, int val){
    ext(n);
    //cout<<n->l<<" "<<n->r<<" "<<val<<endl;
    if(n->l==n->r){
        if(val>0)return n->r+1;
        return n->r;
    }
    if(!n->L){
        return n->r+1;
    }
    int ans=query(n->L,n->L->l,n->L->r,s,e);
    //cout<<ans<<endl;
    if(ans>val){
        return nav(n->L,s,e,val);
    }
    return nav(n->R,s,e,val-ans);


}
pair<lld,lld> arr[1000000];

int n;
tree T;
void init(int N, int A[], int B[])
{
    n=N;
    for(int i=0; i<n; i++)
    {
        arr[i]=pll(A[i],B[i]);

    }
    sort(arr,arr+n);
    T=new ST();
    T->l=0;
    T->r=SQ;
    //cout<<T->r<<endl;
    //S->print(0,n,1);
    //cout<<S->q(2,4,2,3);
    for(int i=0; i<n; i++)
    {
        //cout<<arr[i].second<<endl;
        if(DEBUG==0){
                arr[i].second=arr[i].second*MAXN+i+30;
        }
        //cout<<arr[i].second<<" "<<i<<endl;
        upd(T,arr[i].second,i);
    }
    //cout<<nav(T,0,2,3)<<endl;
}

int can(int M, int K[])
{
    sort(K,K+M);
    if(DEBUG==1){
        int pnt=0;
        priority_queue<int>pq;
        for(int i=0;i<M;i++){
            while(pnt<n && arr[pnt].first<=K[i]){
                pq.push(-arr[pnt].second);
                pnt++;
            }
            while(-pq.top()<K[i]){
                if(pq.empty())return 0;
                pq.pop();
            }
            for(int j=0;j<K[i];j++){
                if(pq.empty())return 0;
                pq.pop();
            }
        }return 1;
    }
    stack<pll>s;
    for(int i=0;i<M;i++){
        int lo,hi;
        lo=-1;
        hi=n;
        while(hi-lo>1){
            int mid=(hi+lo)/2;
            if(arr[mid].first<=K[i]){
                lo=mid;
            }else hi=mid;
        }
        //cout<<lo<<endl;
        //cout<<arr[hi].second/MAXN<<endl;
        lld H=MAXN*(lld)K[i];
        while(!s.empty() && s.top().second<=H){
            s.pop();
        }
        int Group=K[i];

        //cout<<H<<endl;
        //cout<<H<<" B"<<s.size()<<endl;
        while(!s.empty() && query(T,H,s.top().second-1,s.top().first+1,lo)<=Group){
            Group-=query(T,H,s.top().second-1,s.top().first+1,lo);
            H=s.top().second;
            s.pop();
        }
        //cout<<s.size()<<" A "<<H<<endl;

        if(s.empty()){
            //cout<<Q(T,0,SQ,lo)<<"Q"<<endl;
            if(query(T,H,SQ,0,lo)<Group){
                return 0;
            }
            H=nav(T,0,lo,Group+query(T,0,H-1,0,lo));
        }else{
            H=nav(T,s.top().first+1,lo,Group+query(T,0,H-1,s.top().first+1,lo));
        }

        s.push(pll(lo,H));
        //cout<<lo<<" "<<H<<endl;
    }
    return 1;

}

Compilation message (stderr)

teams.cpp: In function 'int Q(tree, lld, lld, int)':
teams.cpp:59:21: warning: conversion to 'int' from 'std::vector<long long int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
         hi=n->v.size();
            ~~~~~~~~~^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:132:25: warning: conversion to 'std::priority_queue<int>::value_type {aka int}' from 'long long int' may alter its value [-Wconversion]
                 pq.push(-arr[pnt].second);
                         ^~~~~~~~~~~~~~~~
teams.cpp:166:69: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         while(!s.empty() && query(T,H,s.top().second-1,s.top().first+1,lo)<=Group){
                                                        ~~~~~~~~~~~~~^~
teams.cpp:167:60: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
             Group-=query(T,H,s.top().second-1,s.top().first+1,lo);
                                               ~~~~~~~~~~~~~^~
teams.cpp:180:73: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
             H=nav(T,s.top().first+1,lo,Group+query(T,0,H-1,s.top().first+1,lo));
                                                            ~~~~~~~~~~~~~^~
teams.cpp:180:34: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
             H=nav(T,s.top().first+1,lo,Group+query(T,0,H-1,s.top().first+1,lo));
                     ~~~~~~~~~~~~~^~

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