Submission #1109146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109146		Pioneer	Teams (IOI15_teams)	C++17	13 / 100	937 ms	257864 KiB

teams

#include "teams.h"
#include "bits/stdc++.h"

using namespace std;

#define pb push_back
#define all(v) v.begin(),v.end()
#define ub upper_bound
#define lb lower_bound
#define sz(s) (int)s.size()
#define pii pair<int,int>
#define F first
#define S second

const int MAX=5e5+10;

int n;
vector<int> a[MAX],b[MAX];

struct segtree{
	vector<int> t[4*MAX];

	void build(int v,int tl,int tr){
		if(tl==tr){
			t[v]=a[tl];
			sort(all(t[v]));
			return;
		}
		int tm=(tl+tr)/2;
		build(2*v,tl,tm);
		build(2*v+1,tm+1,tr);
		t[v].resize(sz(t[2*v])+sz(t[2*v+1]));
		merge(all(t[2*v]),all(t[2*v+1]),t[v].begin());
	}

	int cnt(int v,int l,int r){
		return ub(all(t[v]),r)-lb(all(t[v]),l);
	}

	int get(int v,int tl,int tr,int l,int r,int x){
		if(tl==tr){
			if(x>cnt(v,l,r))return 0;
			return tl;
		}
		int tm=(tl+tr)/2;
		if(cnt(2*v+1,l,r)<x)return get(2*v,tl,tm,l,r,x-cnt(2*v+1,l,r));
		else return get(2*v+1,tm+1,tr,l,r,x);
	}
}t;

struct segtree1{
	vector<int> t[4*MAX];

	void build(int v,int tl,int tr){
		if(tl==tr){
			t[v]=b[tl];
			sort(all(t[v]));
			return;
		}
		int tm=(tl+tr)/2;
		build(2*v,tl,tm);
		build(2*v+1,tm+1,tr);
		t[v].resize(sz(t[2*v])+sz(t[2*v+1]));
		merge(all(t[2*v]),all(t[2*v+1]),t[v].begin());
	}
	
	int get(int v,int tl,int tr,int l,int r,int x){
		if(l>r||tl>r||l>tr)return 0;
		if(l<=tl&&tr<=r){
			// cout<<tl<<" "<<tr<<" "<<x<<" "<<(tr-tl+1)-(lb(all(t[v]),x)-t[v].begin())<<"\n";
			return sz(t[v])-(lb(all(t[v]),x)-t[v].begin());
		}
		int tm=(tl+tr)/2;
		return get(2*v,tl,tm,l,r,x)+get(2*v+1,tm+1,tr,l,r,x);
	}
}z;

void init(int N, int A[], int B[]){
	n=N;
	for(int i=0;i<N;i++){
		a[B[i]].pb(A[i]);
		b[A[i]].pb(B[i]);
		// if(A[i]<=3&&3<=B[i])cout<<A[i]<<" "<<B[i]<<"\n";
	}
	t.build(1,1,n);
	z.build(1,1,n);
	// for(int x:z.t[1])cout<<x<<" ";
	// cout<<"\n";
}

int cnt[MAX],dp[MAX];

int can(int M, int K[]){
	// memset(dp,0,sizeof(dp));
	sort(K,K+M);
	int sum=0;
	vector<int> a;
	for(int i=0;i<M;i++){
		sum+=K[i];
		cnt[K[i]]++;
		a.pb(K[i]);
	}
	if(sum>n){
		for(int x:a)cnt[x]=0;
		return 0;
	}
	sort(all(a));
	a.erase(unique(all(a)),a.end());
	set<int> st;
	set<pii> ev;
	for(int x:a){
		while(!ev.empty()&&ev.begin()->F<=x){
			int y=ev.begin()->S;
			ev.erase(ev.begin());
			if(!st.count(y))continue;
			st.erase(y);
			if(!st.empty()&&*st.begin()<y){
				int val=*(--st.lb(y));
				while(st.lb(y)!=st.end()&&t.get(1,1,n,val+1,*st.lb(y)-1,dp[*st.lb(y)]-dp[val])){
					st.erase(st.lb(y));
				}
				if(st.lb(y)!=st.end())ev.insert({t.get(1,1,n,val+1,*st.lb(y)-1,dp[*st.lb(y)]-dp[val]),*st.lb(y)});
			}
		}
		dp[x]=z.get(1,1,n,1,x,x)-cnt[x]*x;
		// cout<<x<<" "<<dp[x]<<"\n";
		// cerr<<x<<" "<<z.get(1,1,n,1,x,x)<<" "<<dp[x]<<" "<<cnt[x]<<"\n";
		if(!st.empty()){
			// if(x==3)cout<<*st.rbegin()<<"\n";
			dp[x]=min(dp[x],dp[*st.rbegin()]+z.get(1,1,n,*st.rbegin()+1,x,x)-cnt[x]*x);
		}
		// cout<<x<<" "<<dp[x]<<"\n";
		// if(!st.empty())cout<<*st.rbegin()<<"\n";
		if(st.empty()){
			st.insert(x);
		}
		else{
			int prev=*st.rbegin();
			// if(x==2){
			// 	cout<<t.get(1,1,n,prev+1,x-1,dp[x]-dp[prev])<<"\n";
			// }
			if(t.get(1,1,n,prev+1,x-1,dp[x]-dp[prev])<=x)continue;
			ev.insert({t.get(1,1,n,prev+1,x-1,dp[x]-dp[prev]),x});
			st.insert(x);
		}
	}
	for(int x:a){
		cnt[x]=0;
	}
	for(int x:a){
		if(dp[x]<0)return 0;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In member function 'int segtree::cnt(int, int, int)':
teams.cpp:37:25: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   37 |   return ub(all(t[v]),r)-lb(all(t[v]),l);
      |                         ^
teams.cpp: In member function 'int segtree1::get(int, int, int, int, int, int)':
teams.cpp:71:19: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   71 |    return sz(t[v])-(lb(all(t[v]),x)-t[v].begin());
      |                   ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:97:14: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   97 |  vector<int> a;
      |              ^
teams.cpp:18:13: note: shadowed declaration is here
   18 | vector<int> a[MAX],b[MAX];
      |             ^

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