Submission #418196

#	Time	Username	Problem	Language	Result	Execution time	Memory
418196		vanic	Teams (IOI15_teams)	C++14	0 / 100	124 ms	17588 KiB

teams

#include "teams.h"
#include <cmath>
#include <algorithm>

using namespace std;

const int maxn=5e5+5;

struct logaritamska{
	int l[maxn];
	void update(int x, int val){
		for(; x<maxn; x+=(x & -x)){
			l[x]+=val;
		}
	}
	int query(int x){
		int sol=0;
		for(; x>0; x-=(x & -x)){
			sol+=l[x];
		}
		return sol;
	}
};

logaritamska poz, neg;

void init(int n, int a[], int b[]){
	for(int i=0; i<n; i++){
		poz.update(a[i], 1);
		neg.update(b[i]+1, -1);
	}
}

int can(int m, int k[]){
	sort(k, k+m);
	int prosl=0;
	int val1, val2, val3;
	for(int i=0; i<m; i++){
		if(i){
			val1=poz.query(k[i])+neg.query(k[i]);
			val2=neg.query(k[i])-neg.query(k[i-1]);
			val3=max(0, prosl+val2);
			if(val1-val3<k[i]){
				return 0;
			}
			prosl=k[i]+val3;
		}
		else{
			val1=poz.query(k[i])+neg.query(k[i]);
			if(val1<k[i]){
				return 0;
			}
			prosl=k[i];
		}
	}
	return 1;
}

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