Submission #363084

#	Time	Username	Problem	Language	Result	Execution time	Memory
363084		Kevin_Zhang_TW	Jousting tournament (IOI12_tournament)	C++17	100 / 100	188 ms	14688 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) {
		++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;
	}
};

struct segset {
	// [L, R, V]
	set<tuple<int,int,int>> st;
	// [L, i], [i+1, R]
	void split(int i) {
		auto it = st.lower_bound(make_tuple(i+1, -1, -1));
		if (it == begin(st)) return; --it;
		auto [l, r, v] = *it;
		if (r <= i) return;
		assert(l <= i && r > i);
		st.erase(it);
		st.insert(make_tuple(l, i, v));
		st.insert(make_tuple(i+1,r,v));
		DE(l, i, i+1, r);
	}
	void modi(int l, int r, int v) {
		split(l-1), split(r);
		auto it = st.lower_bound(make_tuple(l, -1, -1));
		while (it != end(st)) {
			auto [sl, sr, sv] = *it;
			if (sl > r) break;
			it = st.erase(it);
		}
		DE(l, r, v);
		st.insert(make_tuple(l, r, v));
	}
	int qry(int x) {
		auto it = st.lower_bound(make_tuple(x+1, -1, -1));
		if (it == begin(st)) return -1; --it;
		auto [l, r, v] = *it;
		DE(x, l, r);
		if (r < x) return -1;
		assert(l <= x && r >= x);
		return v;
	}
};
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], sz = r - l;
			l = tree.qry(l), r = tree.qry(r+1) - 1;
			DE(l, r);
			for (auto it = next(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))) ]);
	}

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

Compilation message (stderr)

tournament.cpp: In member function 'void segset::split(int)':
tournament.cpp:52:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   52 |   if (it == begin(st)) return; --it;
      |   ^~
tournament.cpp:52:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   52 |   if (it == begin(st)) return; --it;
      |                                ^~
tournament.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
tournament.cpp:59:3: note: in expansion of macro 'DE'
   59 |   DE(l, i, i+1, r);
      |   ^~
tournament.cpp: In member function 'void segset::modi(int, int, int)':
tournament.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
tournament.cpp:69:3: note: in expansion of macro 'DE'
   69 |   DE(l, r, v);
      |   ^~
tournament.cpp: In member function 'int segset::qry(int)':
tournament.cpp:74:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   74 |   if (it == begin(st)) return -1; --it;
      |   ^~
tournament.cpp:74:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   74 |   if (it == begin(st)) return -1; --it;
      |                                   ^~
tournament.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
tournament.cpp:76:3: note: in expansion of macro 'DE'
   76 |   DE(x, l, r);
      |   ^~
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:94:4: note: in expansion of macro 'DE'
   94 |    DE(l, r);
      |    ^~
tournament.cpp:92:30: warning: unused variable 'sz' [-Wunused-variable]
   92 |    int &l = S[i], &r = E[i], sz = r - l;
      |                              ^~
tournament.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
tournament.cpp:140:2: note: in expansion of macro 'DE'
  140 |  DE(win, pos);
      |  ^~

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