Submission #115532

#	Time	Username	Problem	Language	Result	Execution time	Memory
115532		E869120	Teams (IOI15_teams)	C++14	0 / 100	603 ms	46072 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) {
	size_ = 1; for (int i = 0; i < 128; i++) dat[i].clear();
	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 lef_x, int lim_x, int num) {
	int u = 2; num--;
	while (u < size_ * 2) {
		int G = counts(u, lef_x, 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 -----------------------

int cnte[1 << 19], mid[1 << 19], cntt[1 << 19];

void init(int N, int A[], int B[]) {
	for (int i = 0; i <= 128; i++) { cnte[i] = 0; mid[i] = 0; cntt[i] = 0; }
	for (int i = 0; i < N; i++) { cnte[A[i]]++; cnte[B[i]]++; }
	
	for (int i = 1; i <= N; i++) cnte[i] += cnte[i - 1];
	for (int i = 1; i <= N; i++) { A[i] = cnte[A[i] - 1] + cntt[A[i]]; cntt[A[i]]++; }
	for (int i = 1; i <= N; i++) mid[i] = cnte[i - 1] + A[i];
	for (int i = 1; i <= N; i++) { B[i] = cnte[B[i] - 1] + cntt[B[i]]; cntt[B[i]]++; }
	
	initialize(N * 2 + 1);
	for (int i = 0; i < N; i++) add(A[i], B[i]);
	syncronization();
}

int can(int M, int K[]) {
	sort(K, K + M);
	
	vector<tuple<int, int, int>> V; V.push_back(make_tuple(0, (1 << 30), 0));
	for (int i = 0; i < M; i++) {
		int life = K[i], cx = mid[K[i]];
		while (V.size() >= 1) {
			tuple<int, int, int> F = V[V.size() - 1];
			if (get<1>(F) < mid[K[i]]) { V.pop_back(); continue; }
			
			int E = query(get<0>(F) + 1, mid[K[i]], cx, get<1>(F));
			if (life > E) { life -= E; cx = get<1>(F) + 1; V.pop_back(); }
			else {
				int S = life + query(get<0>(F) + 1, mid[K[i]] - 1, get<0>(F) + 1, mid[K[i]] - 1);
				int cx = getmin(get<0>(F) + 1, mid[K[i]], S);
				V.push_back(make_tuple(mid[K[i]], cx, life));
				life = 0;
				break;
			}
		}
		if (life >= 1) return 0;
		
		/*cout << "Current State" << endl;
		for (int j = 0; j < V.size(); j++) {
			cout << "# "<< j << " : L = " << get<0>(V[j]) << ", R = " << get<1>(V[j]) << ", X = " << get<2>(V[j]) << endl;
		}*/
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int counts(int, int, int)':
teams.cpp:29: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:30: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();
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:90:9: warning: declaration of 'cx' shadows a previous local [-Wshadow]
     int cx = getmin(get<0>(F) + 1, mid[K[i]], S);
         ^~
teams.cpp:81:20: note: shadowed declaration is here
   int life = K[i], cx = mid[K[i]];
                    ^~

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