Submission #65993

#	Time	Username	Problem	Language	Result	Execution time	Memory
65993		gnoor	Teams (IOI15_teams)	C++17	100 / 100	3448 ms	373232 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 used[5100];
int can(int M, int K[]) {
	sort(K,K+M);
	vector<int> x;

	for (int i=0;i<M;i++) x.push_back(K[i]);
	x.resize(unique(x.begin(),x.end())-x.begin());
	int nn=x.size();
	fill(used,used+nn,0);

	int res;
	int ptr=0;
	int cur;
	int ptr2=0;
	for (int i=0;i<M;i++) {
		while (x[ptr]<K[i]) ptr++;
		cur=K[i];
		if (i&&K[i]!=K[i-1]) ptr2=ptr;
		while (cur&&ptr2<nn) {
			res=root[pos[K[i]]]->query(1,n+1,x[ptr2],(ptr2==nn-1)?n+1:x[ptr2+1])-used[ptr2];	
			used[ptr2]+=min(res,cur);
			cur-=min(res,cur);
			if (cur==0) break;
			ptr2++;
		}
		if (cur!=0) return 0;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:62:15: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  int nn=x.size();
         ~~~~~~^~

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