Submission #1108888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108888		Pioneer	Teams (IOI15_teams)	C++17	77 / 100	4045 ms	144720 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{
	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){
			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++){
		b[A[i]].pb(B[i]);
	}
	z.build(1,1,n);
}

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(1,1,n,1,x,x)-cnt[x]*x;
		for(int y:a){
			if(y>=x)break;
			dp[x]=min(dp[x],dp[y]+z.get(1,1,n,y+1,x,x)-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;
}

Compilation message (stderr)

teams.cpp: In member function 'int segtree1::get(int, int, int, int, int, int)':
teams.cpp:39:19: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   39 |    return sz(t[v])-(lb(all(t[v]),x)-t[v].begin());
      |                   ^

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