Submission #65977

#	Time	Username	Problem	Language	Result	Execution time	Memory
65977		gnoor	Teams (IOI15_teams)	C++17	0 / 100	1650 ms	387576 KiB

teams

#include "teams.h"

#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;

struct node {
	int val;
	node *lft,*rgt;

	node(int _val,node *_l=0,node *_r=0): val(_val),lft(_l),rgt(_r) {}

	node* insert(int l,int r,int k) {
		if (k<l||k>=r) return this;
		if (l+1==r) return new node(this->val+1,lft,rgt);
		int m=(l+r)>>1;
		return new node(this->val+1,lft->insert(l,m,k),rgt->insert(m,r,k));
	}

	int query(int l,int r,int ll,int rr) {
		if (rr<=l||ll>=r) return 0;
		if (ll<=l&&rr>=r) return this->val;
		int m=(l+r)>>1;
		return lft->query(l,m,ll,rr)+rgt->query(m,r,ll,rr);
	}
};

node* root[500100];
int pos[500100];
int n;

void init(int N, int A[], int B[]) {
	n=N;
	vector<pair<int,int>> student;
	for (int i=0;i<N;i++) {
		student.push_back({A[i],B[i]});
	}
	sort(student.begin(),student.end());

	root[0]=new node(0);
	root[0]->lft=root[0];
	root[0]->rgt=root[0];
	
	for (int i=1;i<=n;i++) {
		root[i]=root[i-1]->insert(1,N+1,student[i-1].second);
		pos[student[i-1].first]=i;
	}
	for (int i=1;i<=n;i++) {
		if (pos[i]==0) pos[i]=pos[i-1];
	}
}

int can(int M, int K[]) {
	sort(K,K+M);
	int res;
	int leftover=0;
	for (int i=0;i<M;i++) {
		res=root[pos[K[i]]]->query(1,n+1,K[i],n+1);
		if (res<K[i]+leftover) return 0;
		if (i!=M-1) leftover=leftover+K[i]-root[pos[K[i]]]->query(1,n+1,K[i],K[i+1]);
	}
	return 1;
}

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