Submission #289314

#	Time	Username	Problem	Language	Result	Execution time	Memory
289314		user202729	Teams (IOI15_teams)	C++17	77 / 100	4099 ms	197448 KiB

teams

// moreflags=grader.cpp
//
// 10
// what an unexpected bug.
// :(
#include "teams.h"
#include<vector>
#include<queue>
#include<functional>
#include<algorithm>
#if LOCAL
#include<iostream>
#else
#define NDEBUG
#endif
#include<cassert>

struct Persistent{
	struct Node{int value; std::array<int, 2> children;};
	// value is sum of current subtree
	std::vector<Node> data;
	int number;
	Persistent(int number=0): number(number){
		data.resize(number*4);
		for(int node=0; node<(int)data.size()/2; ++node)
			data[node].children={node*2+1, node*2+2};
		// initially root is 0 and all values are 0
	}

	int makeNode(Node node){
		int const result=(int)data.size();
		data.push_back(node);
		return result;
	}

	int set(int node, int left, int right, int index, auto getter /* old -> new */){
		if(left+1==right){
			//if(data[node].value==value) return node;
			return makeNode(Node{getter(data[node].value), {}});
		}
		int const middle=(left+right)>>1;
		auto copy=data[node];
		if(index>=middle){
			copy.value-=data[copy.children[1]].value;
			copy.children[1]=set(copy.children[1], middle, right, index, getter);
			copy.value+=data[copy.children[1]].value;
		}else{
			copy.value-=data[copy.children[0]].value;
			copy.children[0]=set(copy.children[0], left, middle, index, getter);
			copy.value+=data[copy.children[0]].value;
		}
		return makeNode(copy);
	}

	int get(int node, int left, int right, int queryLeft, int queryRight)const{
		if(queryLeft>=right or queryRight<=left) return 0;
		if(queryLeft<=left and right<=queryRight) return data[node].value;
		int const middle=(left+right)>>1;
		return get(data[node].children[0], left, middle, queryLeft, queryRight)+
			get(data[node].children[1], middle, right, queryLeft, queryRight);
	}

	int set(int node, int index, auto getter /* old -> new */){
		return set(node, 0, number, index, getter);
	}
	int get(int node, int queryLeft, int queryRight)const{
		return get(node, 0, number, queryLeft, queryRight);
	}
};

std::vector<std::pair<int, int>> students;
Persistent tree;
std::vector<int> roots;
std::vector<int> bounds;
// students[bounds[i-1]..bounds[i]].left = i

void init(int N, int A[], int B[]) {
	students.clear(); students.reserve(N);
	for(int i=0; i<N; ++i)
		students.push_back({A[i], B[i]});
	std::sort(begin(students), end(students));

	roots.reserve((int)students.size());
	roots.clear();
	roots.push_back(0);
	tree=Persistent(N+1);
	for(auto [left, right]: students){
		assert(right<=N); assert(0<left);
		roots.push_back(
				tree.set(roots.back(), right, [&](int value){return value+1;})
				);
	}

	if(0)
	assert(([&]{
		for(auto root: roots){
			for(int index=0; index<tree.number; ++index)
				std::cerr<<tree.get(root, index, index+1)<<' ';
			std::cerr<<" -- ";
			for(int index=0; index<tree.number; ++index)
				std::cerr<<tree.get(root, index, tree.number)<<' ';
			std::cerr<<'\n';
		}
		return true;
	}()));

	bounds.clear();
	bounds.reserve(N+1);
	for(int index=0; index<(int)students.size(); ++index)
		while((int)bounds.size()<students[index].first)
			bounds.push_back(index);
	while((int)bounds.size()<N+1) bounds.push_back((int)students.size());
}

int can(int M, int K[]) {
	std::sort(K, K+M);
	struct Item{
		int value;
		mutable int count;

		bool operator<(Item other) const{return value>other.value;}
	};
	std::priority_queue<Item> rights;
	//std::map<int, int> rights;


	std::vector<int> splits(K, K+M);
	splits.erase(std::unique(begin(splits), end(splits)), end(splits));

	int last=0;
	for(int index=0; index<M; ++index){
		auto const k=K[index];
		if(k>(int)students.size()) return 0;
		while(not rights.empty() and rights.top().value<k)
			rights.pop();

		auto j=int(std::lower_bound(begin(splits), end(splits), k)-begin(splits));
		assert(splits[j]==k);
#if LOCAL
		if(1)
#else
		if(bounds[k]-last<=(int)splits.size()-j)
#endif
		{
			for(int index=last; index<bounds[k]; ++index)
				if(students[index].second>=k)
					rights.push({students[index].second, 1});
		}else{
			for(; j<(int)splits.size(); ++j){
				int const queryLeft=splits[j];
				int const queryRight=j+1==(int)splits.size() ? tree.number: splits[j+1];
				assert(queryLeft<queryRight);
				int const count=tree.get(roots[bounds[k]], queryLeft, queryRight)-
					tree.get(roots[last], queryLeft, queryRight);
				assert(count>=0);
				assert(count==std::count_if(students.begin()+last, students.begin()+bounds[k],
							[&](auto value){return queryLeft<=value.second and value.second<queryRight;}));
				if(count>0) rights.push({queryLeft, count});
			}
		}

		assert(last<=bounds[k]);
		last=bounds[k];

		int remain=k;
		while(remain){
			if(rights.empty()) return 0;
			if(remain>=rights.top().count){
				remain-=rights.top().count;
				rights.pop();
			}else{
				rights.top().count-=remain;
				break;
			}
		}
	}
	return 1;
}

Compilation message (stderr)

teams.cpp:36:52: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   36 |  int set(int node, int left, int right, int index, auto getter /* old -> new */){
      |                                                    ^~~~
teams.cpp:63:31: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   63 |  int set(int node, int index, auto getter /* old -> new */){
      |                               ^~~~
teams.cpp: In constructor 'Persistent::Persistent(int)':
teams.cpp:23:26: warning: declaration of 'number' shadows a member of 'Persistent' [-Wshadow]
   23 |  Persistent(int number=0): number(number){
      |                          ^
teams.cpp:22:6: note: shadowed declaration is here
   22 |  int number;
      |      ^~~~~~
teams.cpp: In constructor 'Persistent::Persistent(int)':
teams.cpp:28:2: warning: declaration of 'number' shadows a member of 'Persistent' [-Wshadow]
   28 |  }
      |  ^
teams.cpp:22:6: note: shadowed declaration is here
   22 |  int number;
      |      ^~~~~~
teams.cpp: In constructor 'Persistent::Persistent(int)':
teams.cpp:28:2: warning: declaration of 'number' shadows a member of 'Persistent' [-Wshadow]
   28 |  }
      |  ^
teams.cpp:22:6: note: shadowed declaration is here
   22 |  int number;
      |      ^~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:145:12: warning: declaration of 'index' shadows a previous local [-Wshadow]
  145 |    for(int index=last; index<bounds[k]; ++index)
      |            ^~~~~
teams.cpp:131:10: note: shadowed declaration is here
  131 |  for(int index=0; index<M; ++index){
      |          ^~~~~

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