Submission #1084962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084962		the_coding_pooh	Teams (IOI15_teams)	C++14	100 / 100	2861 ms	69304 KiB

teams

#include "teams.h"

#include <bits/stdc++.h>
#define uwu return;
#define OwO return 0;
#define IwI return 1;

using namespace std;


vector <pair<int, int>> intervals;

#define fs first
#define sc second

const int SIZE = 5e5 + 5;

vector <int> BITree[SIZE];

void insert(int l,  int r,  int N){
	for(; l <= N; l += l & (-l)){
		BITree[l].push_back(r);
	}
	return;
}

void init_tree(int N){
	for(int i = 1; i <= N; i++){
		sort(BITree[i].begin(),  BITree[i].end());
	}
	return;
}

int calc(int l,  int r){
	int ans = 0;
	for(; l; l -= (l & -l)){
		ans += BITree[l].end() - lower_bound(BITree[l].begin(), BITree[l].end(), r); 
	}
	return ans;
}

int query(int ll, int lr,  int mnr){
	return calc(lr, mnr) - calc(ll, mnr);
}

void init(int N, int A[], int B[]) {
	for(int i = 0; i < N; i++){
		intervals.push_back({A[i],  B[i]});
		insert(A[i],  B[i],  N);
	}
	sort(intervals.begin(),  intervals.end());
	init_tree(N);
	uwu
}

const int THRESHOLD = 5e2;

int hall[THRESHOLD + 10];

int can(int M, int K[]) {
	vector <int> in_K;
	in_K.push_back(0);
	for(int i = 0; i < M; i++){
		in_K.push_back(K[i]);
	}
	sort(in_K.begin(),  in_K.end());
	if(M > THRESHOLD){
		int ptr = 0;
		priority_queue <int> pq;
		for(auto i:in_K){
			while(ptr < (int) intervals.size() && intervals[ptr].fs <= i){
				pq.push(-intervals[ptr].sc);
				ptr++;
			}
			while(!pq.empty() && -pq.top() < i){
				pq.pop();
			}
			int cnt = i;
			while(cnt--){
				if(pq.empty()) OwO
				pq.pop();
			}
		}
		IwI
	}
	else{
		for(int i = 1; i <= M; i++){
			hall[i] = SIZE;
			for(int j = 0; j < i; j++){
				hall[i] = min(hall[i], hall[j] + query(in_K[j], in_K[i], in_K[i]) - in_K[i]);
			}
			if(hall[i] < 0) OwO
		}
		IwI
	}
}

Compilation message (stderr)

teams.cpp: In function 'int calc(int, int)':
teams.cpp:37:77: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   37 |   ans += BITree[l].end() - lower_bound(BITree[l].begin(), BITree[l].end(), r);
      |                                                                             ^

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