Submission #363062

#	Time	Username	Problem	Language	Result	Execution time	Memory
363062		Kevin_Zhang_TW	Jousting tournament (IOI12_tournament)	C++17	0 / 100	1084 ms	6692 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 100010, LG = 17;

int mx[LG][MAX_N];
// [L, R)
int qry(int l, int r) {
	int lg = __lg(r - l);
	return max(mx[lg][l], mx[lg][r - (1<<lg)]);
}
// make it 1 based
struct bit {
	vector<int> val;
	int n;
	bit(int _n) : n(_n) {
		val.resize(n + 1);
	}
	void add(int i, int v) {
		for (++i;i <= n;i += i&-i)
			val[i] += v;
	}
	int qry(int k) {
		int res = 0;
		for (int i = 1<<LG;i;i>>=1) 
			if ((res | i) <= n && val[res | i] < k)
				k -= val[res |= i];
		return res;
	}
};

int nxt[MAX_N], dp[MAX_N];

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	{
		set<int> alive;
		bit tree(N);
		for (int i = 0;i < N;++i) tree.add(i, 1), alive.insert(i);

		for (int i = 0;i < C;++i) {
			nxt[i] = i;
			int &l = S[i], &r = E[i];
			l = tree.qry(l), r = tree.qry(r);
			for (auto it = alive.lower_bound(l);it != end(alive);) {
				if (*it > r) break;
				tree.add(*it, -1);
				it = alive.erase(it);
			}
		}
		for (int i = 0;i < N;++i) mx[0][i] = K[i];
		for (int d = 1;1 << d <= N;++d) 
			for (int i = 0;i < N;++i)
				mx[d][i] = max(mx[d-1][i], mx[d-1][ min(N - 1, i + (1<<(d-1))) ]);
	}

	for (int i = C-1;i >= 0;--i) {
		int enemy = qry(S[i], E[i]);
		if (enemy > R) continue;
		dp[i] = 1;
		for (int j = i + 1;j < C;++j) {
			if (S[j] <= S[i] && E[j] >= E[i]) {
				dp[i] += dp[j];
				break;
			}
		}
	}
	int win = 0, pos = 0;
	for (int i = 0;i < N;++i) {
		for (int j = 0;j < C;++j) {
			if (S[j] <= i && E[j] >= i) {
				if (chmax(win, dp[j]))
					pos = i;
				break;
			}
		}
	}
	DE(win, pos);
	return pos;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
tournament.cpp:90:2: note: in expansion of macro 'DE'
   90 |  DE(win, pos);
      |  ^~

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