Submission #418129

#	Time	Username	Problem	Language	Result	Execution time	Memory
418129		Jasiekstrz	Teams (IOI15_teams)	C++17	100 / 100	3441 ms	122108 KiB

teams

#include<bits/stdc++.h>
#include "teams.h"
#define fi first
#define se second
using namespace std;
const int NN=5e5;
int pot;
struct Tree
{
	Tree *son[2];
	int l,r;
	vector<int> t;
	Tree(int _l,int _r) : l(_l),r(_r)
	{
		son[0]=son[1]=NULL;
	}
	~Tree()
	{
		delete son[0];
		delete son[1];
	}
	void sort_subtree()
	{
		sort(t.begin(),t.end());
		for(int i:{0,1})
		{
			if(son[i]!=NULL)
				son[i]->sort_subtree();
		}
		return;
	}
	Tree* go(bool dir)
	{
		if(son[dir]==NULL)
		{
			if(!dir)
				son[dir]=new Tree(l,(l+r)/2);
			else
				son[dir]=new Tree((l+r)/2+1,r);
		}
		return son[dir];
	}
	void add(int x,int y)
	{
		t.push_back(y);
		if(l==r)
			return;
		int mid=(l+r)/2;
		if(x<=mid)
			go(0)->add(x,y);
		else
			go(1)->add(x,y);
		return;
	}
	int cnt(int x)
	{
		if(t[0]>x)
			return 0;
		int bg=0,en=t.size()-1;
		while(bg<en)
		{
			int mid=(bg+en+1)/2;
			if(t[mid]<=x)
				bg=mid;
			else
				en=mid-1;
		}
		return bg+1;
	}
	int read_son(int lx,int rx,int ly,int ry,bool dir)
	{
		if(son[dir]!=NULL)
			return son[dir]->read(lx,rx,ly,ry);
		return 0;
	}
	int read(int lx,int rx,int ly,int ry)
	{
		if(lx<=l && r<=rx)
			return cnt(ry)-cnt(ly-1);
		int mid=(l+r)/2;
		int ans=0;
		if(lx<=mid)
			ans+=read_son(lx,rx,ly,ry,0);
		if(mid+1<=rx)
			ans+=read_son(lx,rx,ly,ry,1);
		return ans;
	}
};
int n;
Tree *root;
int t[NN+10];
int dp[NN+10];
vector<int> st;
int get_val(int j,int k)
{
	return dp[j]-(root->read(k,pot,1,t[j]));
}
int when_better(int a,int b)
{
#warning log^3
// TEMPORARY
	int bg=1,en=pot;
	while(bg<en)
	{
		int mid=(bg+en)/2;
		if(get_val(a,mid)<=get_val(b,mid))
			en=mid;
		else
			bg=mid+1;
	}
	if(get_val(a,bg)>get_val(b,bg))
		return pot+1;
	return bg;
}
void init(int N,int A[],int B[])
{
	n=N;
	for(pot=1;pot<n;pot*=2);
	root=new Tree(1,pot);
	for(int i=0;i<n;i++)
		root->add(B[i],A[i]);
	root->sort_subtree();
	return;
}
int can(int M,int K[])
{
	long long sum=0;
	sort(K,K+M);
	for(int i=0;i<M;i++)
	{
		t[i+1]=K[i];
		sum+=K[i];
	}
	if(sum>n)
		return 0;
	st.clear();
	st.push_back(0);
	for(int i=1;i<=M;i++)
	{
		while(st.size()>1 && get_val(st[st.size()-2],t[i])<=get_val(st.back(),t[i]))
			st.pop_back();
		dp[i]=get_val(st.back(),t[i])+(root->read(t[i],pot,1,t[i]))-t[i];
		//cerr<<"dp["<<i<<"]="<<dp[i]<<"\n";
		if(dp[i]<0)
			return 0;
		while(st.size()>1 && when_better(st[st.size()-2],st.back())<=when_better(st.back(),i))
			st.pop_back();
		if(get_val(st.back(),t[i])>get_val(i,t[i]))
			st.push_back(i);
	}
	return 1;
}

Compilation message (stderr)

teams.cpp:100:2: warning: #warning log^3 [-Wcpp]
  100 | #warning log^3
      |  ^~~~~~~
teams.cpp: In member function 'int Tree::cnt(int)':
teams.cpp:59:23: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   59 |   int bg=0,en=t.size()-1;
      |               ~~~~~~~~^~

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