Submission #1109137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109137		Pioneer	Teams (IOI15_teams)	C++17	0 / 100	1517 ms	524288 KiB

teams

#include "teams.h"
#include "bits/stdc++.h"
 
using namespace std;
 
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
 
#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()
 
const int MAX=5e5+10;
 
int n;
vector<int> b[MAX];
 
struct segtree1{
	int t[40*MAX];
	int l[40*MAX],r[40*MAX];
	int cnt;

	segtree1(){
		cnt=0;
		memset(t,0,sizeof(t));
		memset(l,0,sizeof(l));
		memset(r,0,sizeof(r));
	}

	void build(int v,int tl,int tr){
		if(tl==tr)return;
		int tm=(tl+tr)/2;
		l[v]=++cnt,r[v]=++cnt;
		build(l[v],tl,tm);
		build(r[v],tm+1,tr);
	}

	int update(int v,int tl,int tr,int pos){
		if(tl==tr){
			int cur=++cnt;
			t[cur]=t[v]+1;
			return cur;
		}
		int tm=(tl+tr)/2;
		int cur=++cnt;
		if(pos<=tm){
			l[cur]=update(l[v],tl,tm,pos);
			r[cur]=r[v];
		}
		else{
			r[cur]=update(r[v],tm+1,tr,pos);
			l[cur]=l[v];
		}
		t[cur]=t[l[cur]]+t[r[cur]];
		return cur;
	}

	int get(int v,int tl,int tr,int L,int R){
		if(L>R||L>tr||tl>R)return 0;
		if(L<=tl&&tr<=R)return t[v];
		int tm=(tl+tr)/2;
		return get(l[v],tl,tm,L,R)+get(r[v],tm+1,tr,L,R);
	}
}z;

vector<int> roots;
 
void init(int N, int A[], int B[]){
	n=N;
	for(int i=0;i<N;i++){
		b[A[i]].pb(B[i]);
	}
	z.build(0,1,n);
	roots.pb(0);
	for(int i=1;i<=n;i++){
		for(int pos:b[i]){
			if(sz(roots)==i){
				roots.pb(z.update(roots.back(),1,n,pos));
			}
			else{
				int v=roots.back();
				roots.pop_back();
				roots.pb(z.update(v,1,n,pos));
			}
		}
	}	
}
 
int cnt[MAX],dp[MAX];
 
int can(int M, int K[]){
	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)return 0;
	sort(all(a));
	a.erase(unique(all(a)),a.end());
	for(int x:a){
		dp[x]=z.get(roots[x],1,n,x,n);
		for(int y:a){
			if(y>=x)break;
			dp[x]=min(dp[x],dp[y]+z.get(roots[x],1,n,x,n)-z.get(roots[y-1],1,n,x,n)-cnt[x]*x);
		}
		if(dp[x]<0){
			for(int y:a)cnt[y]=0;
			return 0;
		}
	}
	for(int y:a)cnt[y]=0;
	return 1;
}

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