Submission #1035752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035752		noyancanturk	Teams (IOI15_teams)	C++17	100 / 100	1109 ms	330812 KiB

teams

#include "teams.h"

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define popb pop_back
using pii=pair<int,int>;

struct Node{
	int val;
	Node*l,*r;
	Node():val(0),l(0),r(0){}
	Node(int VAL):val(VAL),l(0),r(0){}
	Node(Node*L,Node*R):val((L?L->val:0)+(R?R->val:0)),l(L),r(R){}
};

using pnode=Node*;

int getval(pnode p){
	if(p)return p->val;
	return 0;
}
pnode getl(pnode p){
	if(p)return p->l;
	return 0;
}
pnode getr(pnode p){
	if(p)return p->r;
	return 0;
}

pnode root[500100];

int n,*a,*b;
int P;

pnode update(int l,int r,pnode p){
	if(l==r)return new Node(getval(p)+1);
	int mid=(l+r)>>1;
	if(P<=mid)return new Node(update(l,mid,getl(p)),getr(p));
	return new Node(getl(p),update(mid+1,r,getr(p)));
}

pnode update(int x,pnode p){
	P=x;
	return update(0,n+5,p);
}

int L,R;

int query(int l,int r,pnode p){
	if(!p)return 0;
	if(L<=l&&r<=R)return p->val;
	if(r<L||R<l)return 0;
	int mid=(l+r)>>1;
	return query(l,mid,p->l)+query(mid+1,r,p->r);
}

int query(int x,int y,int l,int r){
	assert(x<=y);
	L=l,R=r;
	return query(0,n+5,root[y])-query(0,n+5,root[x-1]);
}

int cnt;

int getkth(int l,int r,pnode p,pnode q){
	if(l==r)return l;
	int mid=(l+r)>>1;
	int lcnt=getval(getl(q))-getval(getl(p));
	if(cnt<=lcnt){
		return getkth(l,mid,getl(p),getl(q));
	}
	cnt-=lcnt;
	return getkth(mid+1,r,getr(p),getr(q));
}

int getkth(int x,int y,int k){
	assert(x<=y);
	cnt=k;
	return getkth(0,n+5,root[x-1],root[y]);
}

void init(int N, int A[], int B[]) {
	n=N,a=A,b=B;
	int p[N];
	for(int i=0;i<n;i++){
		p[i]=i;
	}
	sort(p,p+n,[&](int i,int j)->bool {
		return a[i]<a[j];
	});
	int j=0;
	for(int i=1;i<=n;i++){
		root[i]=root[i-1];
		while(j<n&&a[p[j]]==i){
			root[i]=update(b[p[j]],root[i]);
			j++;
		}
	}
}

struct state{
	int h,end,cnt;
	state(){}
	state(int H,int END,int CNT):h(H),end(END),cnt(CNT){}
};

int can(int M, int K[]) {
	long long ccnt=0;
	for(int i=0;i<M;i++){
		ccnt+=K[i];
	}
	if(n<ccnt)return 0;
	sort(K,K+M);
	vector<state>st;
	st.pb({0,n,0});
	st.pb({K[0],K[0]-1,query(1,K[0],0,K[0]-1)});
	for(int i=0;i<M;i++){
		int need=K[i];
		while(need){
			int sz=st.size();
			if(sz==1)return 0;
			state cur=st[sz-1],past=st[sz-2];
			int all=getval(root[cur.h])-getval(root[past.h]);
			int coulduse=query(past.h+1,cur.h,0,past.end)-cur.cnt;
			if(need<coulduse){
				cur.cnt+=need;
				if(cur.cnt<all)cur.end=getkth(past.h+1,cur.h,cur.cnt+1)-1;
				else {
					cur.end=past.end;
				}
				if(past.end<=cur.end){
					cur.end=past.end;
					cur.cnt+=past.cnt;
					st.pop_back();
				}
				st.back()=cur;
				need=0;
			}else{
				cur.cnt+=coulduse+past.cnt;
				cur.end=past.end;
				st.popb();
				st.back()=cur;
				need-=coulduse;
			}
		}
		if(i+1<M){
			int nx=K[i+1];
			if(st.back().h==nx)continue;
			while(st.back().end<nx-1){
				st.popb();
			}
			state cur=state(nx,nx-1,query(st.back().h+1,nx,0,nx-1));
			if(st.back().end==cur.end){
				cur.cnt+=st.back().cnt;
				st.popb();
			}
			st.pb(cur);
		}
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:123:18: warning: conversion from 'std::vector<state>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  123 |    int sz=st.size();
      |           ~~~~~~~^~

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