oj.uz

Submission #301942

# Submission time Handle Problem Language Result Execution time Memory
301942 2020-09-18T10:14:28 Z square1001 Teams (IOI15_teams) C++14
77 / 100
 981 ms 524292 KB 
#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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 256 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 256 KB Output is correct
24 Correct 1 ms 256 KB Output is correct
25 Correct 1 ms 256 KB Output is correct
26 Correct 1 ms 256 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 418616 KB Output is correct
2 Correct 511 ms 418616 KB Output is correct
3 Correct 510 ms 418488 KB Output is correct
4 Correct 512 ms 418684 KB Output is correct
5 Correct 499 ms 418616 KB Output is correct
6 Correct 486 ms 418488 KB Output is correct
7 Correct 485 ms 418488 KB Output is correct
8 Correct 483 ms 418580 KB Output is correct
9 Correct 486 ms 418872 KB Output is correct
10 Correct 484 ms 418488 KB Output is correct
11 Correct 492 ms 418680 KB Output is correct
12 Correct 485 ms 418560 KB Output is correct
13 Correct 490 ms 418616 KB Output is correct
14 Correct 500 ms 418568 KB Output is correct
15 Correct 507 ms 418648 KB Output is correct
16 Correct 504 ms 418488 KB Output is correct
17 Correct 486 ms 418616 KB Output is correct
18 Correct 493 ms 418492 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 418488 KB Output is correct
2 Correct 524 ms 418488 KB Output is correct
3 Correct 629 ms 420912 KB Output is correct
4 Correct 516 ms 418816 KB Output is correct
5 Correct 961 ms 418616 KB Output is correct
6 Correct 897 ms 419512 KB Output is correct
7 Correct 500 ms 419512 KB Output is correct
8 Correct 783 ms 419640 KB Output is correct
9 Correct 487 ms 419896 KB Output is correct
10 Correct 484 ms 419256 KB Output is correct
11 Correct 493 ms 419256 KB Output is correct
12 Correct 676 ms 419384 KB Output is correct
13 Correct 981 ms 419768 KB Output is correct
14 Correct 698 ms 421284 KB Output is correct
15 Correct 610 ms 419896 KB Output is correct
16 Correct 600 ms 420024 KB Output is correct
17 Correct 668 ms 419772 KB Output is correct
18 Correct 614 ms 419772 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 772 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -