Submission #1018077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018077		DorostWef	Teams (IOI15_teams)	C++17	100 / 100	2777 ms	128416 KiB

teams

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

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
#define F first
#define S second
const int MXN = 500005, SegN = (1 << 20), LG = 19;
pii a[MXN];
int n;
vector <int> seg[SegN];
bitset <SegN> f;
int e[SegN], ans[SegN];
set <int> vv;

int cnt (int v, int x) {
	if (seg[v].empty())
		return 0;
	return (upper_bound (seg[v].begin(), seg[v].end(), x)) - (upper_bound (seg[v].begin(), seg[v].end(), e[v])) - ans[v];
}

void shift (int v) {
	vv.insert(v);
	if (e[v] > e[v * 2]) {
		e[v * 2] = e[v];
		ans[v * 2] = 0;
	}
	if (e[v] > e[v * 2 + 1]) {
		e[v * 2 + 1] = e[v];
		ans[v * 2 + 1] = 0;
	}
}

vector <int> wef;

int find (int x) {
	int k = x;
	int v = (1 << LG) + (lower_bound (a, a + n, make_pair(x, 0)) - a);
	while (true) {
		while (v % 2 == 0)
			v /= 2;
		wef.clear();
		int few = v;
		while (few > 1) {
			few /= 2;
			wef.push_back(few);
		}
		reverse(wef.begin(), wef.end());
		for (int ff : wef)
			shift (ff);
		int w = cnt(v, x);
		if (w >= k) {
			break;
		} else {
			if (f[v]) {
				return MXN;
			}
			e[v] = x;
			for (int ff : wef) {
				ans[ff] += w;
			}
			ans[v] = 0;
			k -= w;
			v /= 2;
			++v;
		}
	}
	while (v < (1 << LG)) {
		shift (v);
		int w = (cnt (v * 2, x));
		wef.clear();
		int few = v;
		while (few) {
			wef.push_back(few);
			few /= 2;
		}
		if (w >= k) {
			v *= 2;
		} else {
			v *= 2;
			e[v] = x;
			for (int ff : wef)
				ans[ff] += w;
			ans[v] = 0;
			v++;
			k -= w;
		}
	}
	wef.clear();
	int few = v;
	while (few > 1) {
		few /= 2;
		wef.push_back(few);
	}
	int w = 1;
	e[v] = x;
	for (int ff : wef)
		ans[ff] += w;
	ans[v] = 0;
	return (v - (1 << LG));
}

void init(int N, int A[], int B[]) {
	for (int i = 0; i <= 20; i++) {
		f[(1 << i) - 1] = true;
	}
	n = N;
	for (int i = 0; i < n; i++) {
		a[i].F = B[i];
		a[i].S = A[i];
	}
	sort (a, a + n);
	int sum = 0;
	for (int i = SegN - 1; i >= 1; i--) {
		if (i >= (1 << LG)) {
			if ((i - (1 << LG)) < n) {
				seg[i].reserve(1);
				seg[i].resize(1);
				seg[i][0] = a[i - (1 << LG)].S;
			}
		} else {
			seg[i].reserve((int)seg[i << 1].size() + (int)seg[i << 1 | 1].size());
			seg[i].resize((int)seg[i << 1].size() + (int)seg[i << 1 | 1].size());
			sum += seg[i].size();
			merge (seg[i << 1].begin(), seg[i << 1].end(), seg[i << 1 | 1].begin(), seg[i << 1 | 1].end(), seg[i].begin());
		}
	}
}

int can(int M, int K[]) {
	vv.clear();
	sort (K, K + M);
	bool h = true;
	int st = 0;
	for (int i = 0; i < M; i++) {
		st = find (K[i]);
		if (st > n) 
			h = false;
		else if (a[st].F < K[i])
			h = false;
	}
	for (int v : vv) {
		e[v] = 0;
		ans[v] = 0;
		e[v << 1] = 0;
		ans[v << 1] = 0;
		e[v << 1 | 1] = 0;
		ans[v << 1 | 1] = 0;
	}
	return h;
}

Compilation message (stderr)

teams.cpp: In function 'int cnt(int, int)':
teams.cpp:21:110: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   21 |  return (upper_bound (seg[v].begin(), seg[v].end(), x)) - (upper_bound (seg[v].begin(), seg[v].end(), e[v])) - ans[v];
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
teams.cpp: In function 'int find(int)':
teams.cpp:40:20: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   40 |  int v = (1 << LG) + (lower_bound (a, a + n, make_pair(x, 0)) - a);
      |          ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:126:23: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  126 |    sum += seg[i].size();
      |                       ^

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