Submission #1108891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108891		Pioneer	Teams (IOI15_teams)	C++17	77 / 100	4103 ms	127280 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(){
		for(int i=n;i<n+n;i++)sort(all(t[i]));
		for(int v=n-1;v>=1;v--){
			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 l,int r,int x){
		int res=0;
		l+=n,r+=n;
		for(;l<r;l/=2,r/=2){
			if(l&1){
				res+=sz(t[l])-(lb(all(t[l]),x)-t[l].begin());
				l++;
			}
			if(r&1){
				r--;
				res+=sz(t[r])-(lb(all(t[r]),x)-t[r].begin());
			}
		}
		return res;
	}
}z;

void init(int N, int A[], int B[]){
	n=N;
	for(int i=0;i<N;i++){
		z.t[A[i]+N-1].pb(B[i]);
	}
	z.build();
}

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(0,x,x)-cnt[x]*x;
		for(int y:a){
			if(y>=x)break;
			dp[x]=min(dp[x],dp[y]+z.get(y,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)':
teams.cpp:36:48: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   36 |     res+=sz(t[l])-(lb(all(t[l]),x)-t[l].begin());
      |                                                ^
teams.cpp:41:48: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   41 |     res+=sz(t[r])-(lb(all(t[r]),x)-t[r].begin());
      |                                                ^

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