Submission #115524

#	Time	Username	Problem	Language	Result	Execution time	Memory
115524		E869120	Teams (IOI15_teams)	C++14	0 / 100	465 ms	33016 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;

// ------------------------ Segtree Library ----------------------

int size_ = 1;
vector<int> dat[1 << 19];

void initialize(int sz) {
	while (size_ <= sz) size_ *= 2;
}

void add(int px, int py) {
	py += size_; dat[py].push_back(px);
	while (py >= 2) {
		py >>= 1;
		dat[py].push_back(px);
	}
}

void syncronization() {
	for (int i = 1; i < size_ * 2; i++) sort(dat[i].begin(), dat[i].end());
}

int counts(int u, int lx, int rx) {
	// 閉区間
	int pos1 = lower_bound(dat[u].begin(), dat[u].end(), lx) - dat[u].begin();
	int pos2 = lower_bound(dat[u].begin(), dat[u].end(), rx + 1) - dat[u].begin();
	return (pos2 - pos1);
}

int query_(int lx, int rx, int ly, int ry, int a, int b, int u) {
	if (ly <= a && b <= ry) return counts(u, lx, rx);
	if (b <= ly || ry <= a) return 0;
	int s1 = query_(lx, rx, ly, ry, a, (a + b) >> 1, u * 2);
	int s2 = query_(lx, rx, ly, ry, (a + b) >> 1, b, u * 2 + 1);
	return s1 + s2;
}

int query(int lx, int rx, int ly, int ry) {
	// 閉区間
	return query_(lx, rx, ly, ry + 1, 0, size_, 1);
}

int getmin(int lim_x, int num) {
	int u = 2; num--;
	while (u < size_ * 2) {
		int G = counts(u, 0, lim_x);
		if (G <= num) { num -= G; u++; u *= 2; }
		else { u *= 2; }
	}
	if (u == (size_ << 2) - 2) return (1 << 30);
	return (u >> 1) - size_;
}

// ------------------------ Segree Library -----------------------

void init(int N, int A[], int B[]) {
	initialize(N);
	for (int i = 0; i < N; i++) add(A[i], B[i]);
	syncronization();
}

int can(int M, int K[]) {
	sort(K, K + M);
	
	int cx = 0, cnt = 0;
	for (int i = 0; i < M; i++) {
		if (cx < K[i]) cnt = query(0, cx - 1, 0, cx - 1);
		else {
			if (K[i - 1] + 1 <= K[i] - 1) cnt += query(K[i - 1] + 1, K[i - 1] + 1, K[i] - 1, K[i] - 1);
		}
		
		cnt += K[i];
		int G = getmin(K[i], cnt);
		//cout << "Query : lim_x = " << K[i] << ", cnt = " << cnt << " -> Answer = " << G << endl;
		if (G == (1 << 30)) return 0;
		
		cx = G;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int counts(int, int, int)':
teams.cpp:28:59: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
  int pos1 = lower_bound(dat[u].begin(), dat[u].end(), lx) - dat[u].begin();
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
teams.cpp:29:63: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
  int pos2 = lower_bound(dat[u].begin(), dat[u].end(), rx + 1) - dat[u].begin();
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

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