oj.uz

Submission #61688

# Submission time Handle Problem Language Result Execution time Memory
61688 2018-07-26T10:35:53 Z aome Jousting tournament (IOI12_tournament) C++17
100 / 100
 158 ms 5792 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

struct SegmentTree {
	int T[4 * N];

	#define mid ((l + r) >> 1)

	void build(int i, int l, int r) {
		if (l == r) { T[i] = 1; return; }
		build(i << 1, l, mid);
		build(i << 1 | 1, mid + 1, r);
		T[i] = T[i << 1] + T[i << 1 | 1];
	}

	void upd(int i, int l, int r, int p) {
		if (l == r) { T[i] = 0; return; }
		if (mid >= p) upd(i << 1, l, mid, p);
		else upd(i << 1 | 1, mid + 1, r, p);
		T[i] = T[i << 1] + T[i << 1 | 1];
	}

	int get(int i, int l, int r, int k) {
		if (l == r) return l;
		if (T[i << 1] >= k) return get(i << 1, l, mid, k);
		else return get(i << 1 | 1, mid + 1, r, k - T[i << 1]); 
	}

	#undef mid
} IT;

struct Seg {
	int l, r;
	pair<int, int> v;

	bool operator < (const Seg& rhs) const {
		return l > rhs.l;
	}
};

pair<int, int> a[N];
pair<int, int> bit[N];

void upd(int x, pair<int, int> y) {
	for (int i = x; i < N; i += i & -i) bit[i] = max(bit[i], y);
}

pair<int, int> get(int x) {
	pair<int, int> ret = {0, 0};
	for (int i = x; i > 0; i -= i & -i) ret = max(ret, bit[i]);
	return ret;
}

int GetBestPosition(int n, int C, int R, int *K, int *S, int *E) {
	vector<Seg> seg;
	IT.build(1, 0, n - 1);
	for (int i = 0; i < n; ++i) a[i] = {0, -i};
	for (int i = 0; i < C; ++i) {
		vector<int> vec;
		for (int j = S[i]; j <= E[i]; ++j) {
			vec.push_back(IT.get(1, 0, n - 1, j + 1));
		}
		int l = vec[0];
		for (auto j : vec) a[j].first++;
		for (auto j : vec) {
			a[vec[0]] = max(a[vec[0]], a[j]);
		}
		int r = (E[i] == (IT.T[1] - 1)) ? n - 1 : (IT.get(1, 0, n - 1, E[i] + 2) - 1);
		seg.push_back({l, r, a[vec[0]]});
		for (int j = 1; j < vec.size(); ++j) {
			IT.upd(1, 0, n - 1, vec[j]);
		}
	}
	vector<Seg> seg2;
	for (int i = 0; i < (n - 1); ++i) {
		if (K[i] > R) continue;
		int r = i;
		while (r < (n - 1) && K[r] <= R) r++;
		seg2.push_back({i, r, make_pair(0, 0)});
		i = r;
	}
	sort(seg.begin(), seg.end());
	sort(seg2.begin(), seg2.end());
	// cout << "#seg\n";
	// for (auto i : seg) cout << i.l << ' ' << i.r << ' ' << i.v.first << ' ' << i.v.second << '\n';
	// cout << "#seg2\n";
	// for (auto i : seg2) cout << i.l << ' ' << i.r << '\n';
	int ptr = 0;
	pair<int, int> res = {0, 0};
	for (auto i : seg2) {
		while (ptr < seg.size() && seg[ptr].l >= i.l) {
			upd(seg[ptr].r + 1, seg[ptr].v), ++ptr;
		}
		res = max(res, get(i.r + 1));
	}
	return -res.second;
}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:73:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j < vec.size(); ++j) {
                   ~~^~~~~~~~~~~~
tournament.cpp:94:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (ptr < seg.size() && seg[ptr].l >= i.l) {
          ~~~~^~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 412 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 3 ms 640 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 7 ms 956 KB Output is correct
3 Correct 5 ms 956 KB Output is correct
4 Correct 9 ms 980 KB Output is correct
5 Correct 9 ms 980 KB Output is correct
6 Correct 8 ms 980 KB Output is correct
7 Correct 7 ms 980 KB Output is correct
8 Correct 8 ms 996 KB Output is correct
9 Correct 5 ms 996 KB Output is correct
10 Correct 12 ms 996 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 2924 KB Output is correct
2 Correct 131 ms 5792 KB Output is correct
3 Correct 61 ms 5792 KB Output is correct
4 Correct 119 ms 5792 KB Output is correct
5 Correct 106 ms 5792 KB Output is correct
6 Correct 145 ms 5792 KB Output is correct
7 Correct 115 ms 5792 KB Output is correct
8 Correct 158 ms 5792 KB Output is correct
9 Correct 37 ms 5792 KB Output is correct
10 Correct 74 ms 5792 KB Output is correct