oj.uz

Submission #105176

# Submission time Handle Problem Language Result Execution time Memory
105176 2019-04-10T22:05:26 Z eriksuenderhauf Jousting tournament (IOI12_tournament) C++11
100 / 100
 189 ms 9004 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
//#include "grader.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long int ll;
const int MAXN = 2e5 + 5;
int n, BIT[MAXN], sm[MAXN], cnt[MAXN];
set<int> act;

int sum(int ind) {
	ind++;
	int ret = 0;
	while (ind > 0) {
		ret += BIT[ind];
		ind -= ind & -ind;
	}
	return ret;
}

void upd(int ind, int val) {
	ind++;
	while (ind <= n) {
		BIT[ind] += val;
		ind += ind & -ind;
	}
}

int qry(int val) {
	int lo = 0, hi = n - 1, ret = -1;
	while (lo <= hi) {
		int mi = (lo + hi) / 2;
		if (sum(mi) <= val)
			ret = mi, lo = mi + 1;
		else
			hi = mi - 1;
	}
	return ret;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	n = N;
	for (int i = 0; i < n; i++) {
		sm[i] = sm[i - 1];
		if (i < n - 1 && K[i] > R)
			sm[i]++;
	}
	for (int i = 0; i < n; i++) {
		upd(i, 1);
		act.insert(i);
	}
	for (int i = 0; i < C; i++) {
		int l = qry(S[i]) + 1, r = qry(E[i] + 1);
		vi tmp;
		for (auto it = act.find(l); it != act.end() && *it <= r; it++)
			tmp.pb(*it);
		for (int j = 0; j < tmp.size(); j++) {
			upd(tmp[j], -1);
			act.erase(tmp[j]);
		}
		upd(l, 1);
		act.insert(l);
		if (sm[l - 1] == sm[r - 1])
			cnt[l]++, cnt[r + 1]--;
	}
	pii ret = {0, 0};
	for (int i = 0; i < n; i++) {
		cnt[i] += cnt[i - 1];
		ret = max(ret, {cnt[i], -i});
	}
	return -ret.se;
}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:64:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < tmp.size(); j++) {
                   ~~^~~~~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 9 ms 896 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 9 ms 768 KB Output is correct
5 Correct 6 ms 640 KB Output is correct
6 Correct 8 ms 768 KB Output is correct
7 Correct 8 ms 768 KB Output is correct
8 Correct 8 ms 896 KB Output is correct
9 Correct 4 ms 768 KB Output is correct
10 Correct 13 ms 768 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 4472 KB Output is correct
2 Correct 146 ms 8952 KB Output is correct
3 Correct 64 ms 7444 KB Output is correct
4 Correct 129 ms 8952 KB Output is correct
5 Correct 134 ms 8696 KB Output is correct
6 Correct 189 ms 8312 KB Output is correct
7 Correct 135 ms 8952 KB Output is correct
8 Correct 129 ms 9004 KB Output is correct
9 Correct 54 ms 7416 KB Output is correct
10 Correct 73 ms 7316 KB Output is correct