Submission #676039

#	Time	Username	Problem	Language	Result	Execution time	Memory
676039		jamezzz	Teams (IOI15_teams)	C++17	100 / 100	1858 ms	144320 KiB

teams

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

#define fi first
#define se second
#define pf printf
#define pb push_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define lb(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define ub(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
typedef pair<int,int> ii;

#define maxn 500005

struct node{
	int s,e,m;vector<int> v;
	node *l,*r;
	node(int _s,int _e){
		s=_s,e=_e,m=(s+e)>>1;
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	void add(int x,int nv){
		v.pb(nv);
		if(s==e)return;
		if(x<=m)l->add(x,nv);
		else r->add(x,nv);
	}
	void init(){
		sort(all(v));
		if(s!=e)l->init(),r->init();
	}
	inline int get(int a,int b){
		return ub(v,b)-lb(v,a);
	}
	int qry(int x,int y,int a,int b){
		if(s==x&&e==y)return get(a,b);
		if(y<=m)return l->qry(x,y,a,b);
		if(x>m)return r->qry(x,y,a,b);
		return l->qry(x,m,a,b)+r->qry(m+1,y,a,b);
	}
	int qryp(int a,int b,int n){
		if(s==e)return s;
		int g=r->get(a,b);
		if(n-g>0){
			return l->qryp(a,b,n-g);
		}
		return r->qryp(a,b,n);
	}
}*rt=new node(1,maxn);

void init(int N,int A[],int B[]){
	for(int i=0;i<N;++i)rt->add(B[i],A[i]);
	rt->init();
}

map<int,int> good;
priority_queue<ii,vector<ii>,greater<ii>> rem;

void create(int i){
	auto b=good.find(i);
	auto a=prev(b);
	int d=b->se-a->se;
	int c=rt->qryp(a->fi+1,b->fi,d)+1;
	rem.push({c,b->fi});
}

void process(int K){
	while(!rem.empty()&&rem.top().fi<=K){
		auto[_,i]=rem.top();
		rem.pop();
		
		auto it=good.find(i);
		if(it==good.end())continue;
		
		auto nit=next(it);
		int nx=-1;
		if(nit!=good.end())nx=nit->fi;
		
		good.erase(it);
		if(nx!=-1)create(nx);
	}
}

void insert(int K,int v){
	good[K]=v;
	if(sz(good)==1)return;
	create(K);
}

int can(int M,int K[]){
	good.clear();
	while(!rem.empty())rem.pop();
	
	sort(K,K+M);
	int acc=0;
	for(int i=0;i<M;++i){
		acc+=K[i];
		if(i!=M-1&&K[i]==K[i+1])continue;
		
		process(K[i]);
		
		int dp=rt->qry(K[i],maxn,1,K[i]);
		if(!good.empty()){
			auto it=--good.end();
			dp=min(dp,it->se+rt->qry(K[i],maxn,it->fi+1,K[i]));
		}
		dp-=acc;
		
		//pf("K: %d, dp: %d\n",K[i],dp);
		
		if(dp<0)return 0;
		
		insert(K[i],dp);
		
		acc=0;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In member function 'int node::get(int, int)':
teams.cpp:35:17: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   35 |   return ub(v,b)-lb(v,a);
      |                 ^

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