제출 #363077

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
363077		Kevin_Zhang_TW	마상시합 토너먼트 (IOI12_tournament)	C++17	49 / 100	1043 ms	6636 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 res =0 ;
	for (int i = l;i < r;++i) chmax(res, mx[0][i]);
	return res;

	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;
	}
};

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))) ]);
	}

	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;
				DE(i, dp[j]);
				break;
			}
		}
	}
	DE(win, pos);
	return pos;
}

컴파일 시 표준 에러 (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:62:4: note: in expansion of macro 'DE'
   62 |    DE(l, r);
      |    ^~
tournament.cpp:60:30: warning: unused variable 'sz' [-Wunused-variable]
   60 |    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:93:5: note: in expansion of macro 'DE'
   93 |     DE(i, dp[j]);
      |     ^~
tournament.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
tournament.cpp:98:2: note: in expansion of macro 'DE'
   98 |  DE(win, pos);
      |  ^~

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