Submission #301942

#	Time	Username	Problem	Language	Result	Execution time	Memory
301942		square1001	Teams (IOI15_teams)	C++14	77 / 100	981 ms	524292 KiB

teams

#include "teams.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const int inf = 1012345678;
class data_structure {
private:
	int N, sz;
	vector<int> sarr;
	vector<vector<int> > lc, rc;
	int query(int a, int b, int x, int k, int l, int r) {
		if(a <= l && r <= b) return x;
		if(r <= a || b <= l) return 0;
		int lres = (lc[k][x - 1] != 0 ? query(a, b, lc[k][x - 1], k * 2, l, (l + r) >> 1) : 0);
		int rres = (rc[k][x - 1] != 0 ? query(a, b, rc[k][x - 1], k * 2 + 1, (l + r) >> 1, r) : 0);
		return lres + rres;
	}
public:
	data_structure() : sz(0), sarr(), lc(), rc() {};
	data_structure(vector<int> arr) {
		N = arr.size();
		sz = 1;
		int depth = 0;
		while(sz < N) {
			sz *= 2;
			++depth;
		}
		sarr = arr;
		sort(sarr.begin(), sarr.end());
		vector<vector<pair<int, int> > > sseq(sz * 2);
		for(int i = 0; i < N; ++i) {
			sseq[sz + i].push_back(make_pair(arr[i], i));
		}
		for(int i = sz - 1; i >= 1; --i) {
			sseq[i].resize(sseq[i * 2].size() + sseq[i * 2 + 1].size());
			merge(sseq[i * 2].begin(), sseq[i * 2].end(), sseq[i * 2 + 1].begin(), sseq[i * 2 + 1].end(), sseq[i].begin());
		}
		lc = vector<vector<int> >(sz);
		rc = vector<vector<int> >(sz);
		for(int i = 0; i < depth; ++i) {
			for(int j = 0; j < 1 << i; ++j) {
				int idx = (1 << i) + j;
				int mid = ((2 * j + 1) << (depth - i - 1));
				lc[idx].resize(sseq[idx].size());
				rc[idx].resize(sseq[idx].size());
				int lcnt = 0, rcnt = 0;
				for(int k = 0; k < int(sseq[idx].size()); ++k) {
					if(sseq[idx][k].second < mid) ++lcnt;
					else ++rcnt;
					lc[idx][k] = lcnt;
					rc[idx][k] = rcnt;
				}
			}
		}
	}
	int count_range(int l, int r, int x) {
		// calculate number of "a[i] < x" in l <= i < r
		int ptr = lower_bound(sarr.begin(), sarr.end(), x) - sarr.begin();
		if(l == 0 && r == N) return ptr;
		if(ptr == 0) return 0;
		return query(l, r, ptr, 1, 0, sz);
	}
};
int N; vector<int> A, B; data_structure ds;
int threshold; vector<vector<int> > sumcnt;
vector<int> transform(int len, vector<int> arr, vector<int> perm) {
	vector<int> res(len);
	for(int i = 0; i < len; ++i) {
		res[i] = arr[perm[i]];
	}
	return res;
}
void init(int N_, int A_[], int B_[]) {
	N = N_;
	A = vector<int>(A_, A_ + N);
	B = vector<int>(B_, B_ + N);
	vector<int> perm(N);
	for(int i = 0; i < N; ++i) {
		perm[i] = i;
	}
	sort(perm.begin(), perm.end(), [&](int i, int j) { return A[i] != A[j] ? A[i] < A[j] : B[i] < B[j]; });
	A = transform(N, A, perm);
	B = transform(N, B, perm);
	ds = data_structure(B);
	threshold = min(N, 100000000 / N);
	sumcnt = vector<vector<int> >(threshold + 1, vector<int>(N + 1));
	for(int i = 0; i <= threshold; ++i) {
		for(int j = 0; j < N; ++j) {
			sumcnt[i][j + 1] = sumcnt[i][j] + (B[j] < i ? 1 : 0);
		}
	}
}
int can(int M, int K[]) {
	long long sum = 0;
	for(int i = 0; i < M; ++i) {
		sum += K[i];
	}
	if(sum > N) {
		return 0;
	}
	vector<int> SK(K, K + M);
	sort(SK.begin(), SK.end());
	vector<int> CK;
	int cnt = 0;
	for(int i = 1; i <= M; ++i) {
		++cnt;
		if(i == M || SK[i - 1] != SK[i]) {
			CK.push_back(cnt);
			cnt = 0;
		}
	}
	SK.erase(unique(SK.begin(), SK.end()), SK.end());
	int S = SK.size();
	vector<int> rem(S + 1);
	for(int i = 0; i < S; ++i) {
		int pl = lower_bound(A.begin(), A.end(), (i == 0 ? 0 : SK[i - 1] + 1)) - A.begin();
		int pr = lower_bound(A.begin(), A.end(), SK[i] + 1) - A.begin();
		vector<int> clist(S + 1);
		for(int j = i; j < S; ++j) {
			if(SK[j] <= threshold) {
				clist[j] = sumcnt[SK[j]][pr] - sumcnt[SK[j]][pl];
			}
			else {
				clist[j] = ds.count_range(pl, pr, SK[j]);
			}
		}
		clist[S] = pr - pl;
		for(int j = i + 1; j <= S; ++j) {
			rem[j] += clist[j] - clist[j - 1];
		}
		int need = CK[i] * SK[i];
		for(int j = i + 1; j <= S; ++j) {
			int use = min(rem[j], need);
			rem[j] -= use;
			need -= use;
		}
		if(need > 0) {
			return 0;
		}
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In constructor 'data_structure::data_structure(std::vector<int>)':
teams.cpp:23:15: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   23 |   N = arr.size();
      |       ~~~~~~~~^~
teams.cpp: In member function 'int data_structure::count_range(int, int, int)':
teams.cpp:60:54: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   60 |   int ptr = lower_bound(sarr.begin(), sarr.end(), x) - sarr.begin();
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:115:17: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  115 |  int S = SK.size();
      |          ~~~~~~~^~
teams.cpp:118:74: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  118 |   int pl = lower_bound(A.begin(), A.end(), (i == 0 ? 0 : SK[i - 1] + 1)) - A.begin();
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
teams.cpp:119:55: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  119 |   int pr = lower_bound(A.begin(), A.end(), SK[i] + 1) - A.begin();
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

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