Submission #393888

#	Time	Username	Problem	Language	Result	Execution time	Memory
393888		rainboy	Jousting tournament (IOI12_tournament)	C11	100 / 100	79 ms	2952 KiB

tournament

#define N	100000
#define N_	(1 << 17)

int st[N_ * 2], n_;

int get(int l, int k) {
	int r = n_ - 1;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((l & 1) == 1) {
			if (k >= st[l])
				k -= st[l];
			else {
				while (l < n_)
					if (k < st[l << 1 | 0])
						l = l << 1 | 0;
					else
						k -= st[l << 1 | 0], l = l << 1 | 1;
				return l - n_;
			}
			l++;
		}
	return n_;
}

void build(int n) {
	int i;

	for (i = 0; i < n; i++)
		st[n_ + i] = 1;
	for (i = n_ - 1; i > 0; i--)
		st[i] = st[i << 1 | 0] + st[i << 1 | 1];
}

void remove_(int i) {
	for (i += n_; i > 0; i >>= 1)
		st[i]--;
}

int ft[N];

void update(int i, int n, int x) {
	while (i < n) {
		ft[i] += x;
		i |= i + 1;
	}
}

int query(int i) {
	int x = 0;

	while (i >= 0) {
		x += ft[i];
		i &= i + 1, i--;
	}
	return x;
}

int GetBestPosition(int n, int m, int r, int *aa, int *ll, int *rr) {
	static int rr_[N];
	int n1, h, i, k_, i_;

	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	build(n);
	n1 = n;
	for (h = 0; h < m; h++) {
		int k = rr[h] - ll[h];

		ll[h] = get(0, ll[h]), rr[h] = (rr[h] == n1 - 1 ? n : get(0, rr[h] + 1)) - 1;
		while (k--)
			remove_(get(ll[h] + 1, 0));
		n1 -= rr[h] - ll[h];
	}
	rr_[n - 1] = n - 1;
	for (i = n - 2; i >= 0; i--)
		rr_[i] = aa[i] > r ? i : rr_[i + 1];
	build(n);
	k_ = -1, i_ = -1;
	for (h = 0; h < m; h++)
		if (rr_[ll[h]] >= rr[h])
			update(ll[h], n, 1), update(rr[h] + 1, n, -1);
		else
			while ((i = get(ll[h], 0)) <= rr[h]) {
				int k = query(i);

				if (k_ < k || k_ == k && i_ > i)
					k_ = k, i_ = i;
				remove_(i);
			}
	return i_;
}

Compilation message (stderr)

tournament.c: In function 'GetBestPosition':
tournament.c:88:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   88 |     if (k_ < k || k_ == k && i_ > i)
      |                   ~~~~~~~~^~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51