Submission #590236

#	Time	Username	Problem	Language	Result	Execution time	Memory
590236		AlperenT	Teams (IOI15_teams)	C++17	0 / 100	4011 ms	48516 KiB

teams

#include <bits/stdc++.h>
// #include "teams.h"

using namespace std;

const int N = 5e5 + 5;
int B_SIZE, B_CNT;

int n;

pair<int, int> arr[N];

vector<pair<int, int>> block[N];

vector<int> blockr[N];

void init(int N_, int A[], int B[]){
	n = N_;

	B_SIZE = (int)sqrt(n) + 1, B_CNT = (n + B_SIZE - 1) / B_SIZE;

	for(int i = 0; i < n; i++) arr[i] = {A[i], B[i]};

	sort(arr, arr + n);

	for(int i = 0; i < n; i++) block[i / B_SIZE].push_back(arr[i]), blockr[i / B_SIZE].push_back(arr[i].second);

	for(int i = 0; i < B_CNT; i++) sort(blockr[i].begin(), blockr[i].end());
}

int can(int m, int k[]){
	sort(k, k + m, greater<int>());

	pair<int, int> ptr = {B_CNT - 1, (int)block[B_CNT - 1].size() - 1};

	for(int cur = 0; cur < m; cur++){
		int rem = k[cur];

		while(rem > 0){
			if(ptr.second == -1 || block[ptr.first].front().first > k[cur]){
				if(ptr.first == 0) return 0;
				else ptr = {ptr.first - 1, (int)block[ptr.first - 1].size() - 1};

				continue;
			}
			else if(block[ptr.first].back().first <= k[cur] && ptr.second == (int)block[ptr.first].size() - 1){
				int cnt = (int)blockr[ptr.first].size() - (lower_bound(blockr[ptr.first].begin(), blockr[ptr.first].end(), k[cur]) - blockr[ptr.first].begin());

				if(cnt < rem){
					rem -= cnt;
					ptr.second = -1;
					continue;
				}
			}
			
			if(block[ptr.first][ptr.second].first <= k[cur] && block[ptr.first][ptr.second].second >= k[cur]) rem--;
			ptr.second--;
		}
	}

	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:47:45: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   47 |     int cnt = (int)blockr[ptr.first].size() - (lower_bound(blockr[ptr.first].begin(), blockr[ptr.first].end(), k[cur]) - blockr[ptr.first].begin());
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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