oj.uz

Submission #393888

# Submission time Handle Problem Language Result Execution time Memory
393888 2021-04-24T18:54:50 Z rainboy Jousting tournament (IOI12_tournament) C
100 / 100
 79 ms 2952 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 208 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 4 ms 440 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 4 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 4 ms 332 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1500 KB Output is correct
2 Correct 78 ms 2884 KB Output is correct
3 Correct 36 ms 2036 KB Output is correct
4 Correct 77 ms 2952 KB Output is correct
5 Correct 75 ms 2872 KB Output is correct
6 Correct 61 ms 2732 KB Output is correct
7 Correct 76 ms 2892 KB Output is correct
8 Correct 79 ms 2884 KB Output is correct
9 Correct 33 ms 1852 KB Output is correct
10 Correct 33 ms 2228 KB Output is correct