제출 #885409

#제출 시각아이디문제언어결과실행 시간메모리
885409chanhchuong123마상시합 토너먼트 (IOI12_tournament)C++14
0 / 100
29 ms14700 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second const int MAX = 100010; int N, C, R; int K[MAX]; int S[MAX]; int E[MAX]; int ll[MAX]; int rr[MAX]; int bit[MAX]; int rmq[17][MAX]; pair<int, int> pp[MAX]; long long st[MAX << 2]; long long lz[MAX << 2]; void update(int id, int delta) { for (; id <= N; id += id & -id) bit[id] += delta; } int getPos(int k) { int pos = 0; for (int j = 31 - __builtin_clz(N); j >= 0; --j) if (pos + (1 << j) <= N) { if (bit[pos + (1 << j)] <= k) { pos += 1 << j; k -= bit[pos]; } } return pos; } void push(int id) { if (lz[id] != 0) { st[id << 1] += lz[id]; st[id << 1 | 1] += lz[id]; lz[id << 1] += lz[id]; lz[id << 1 | 1] += lz[id]; lz[id] = 0; } } void update(int id, int l, int r, int u, int v, int d) { if (l > v || r < u) return; if (l >= u && r <= v) { st[id] += d; lz[id] += d; return; } int mid = l + r >> 1; push(id); update(id << 1, l, mid, u, v, d); update(id << 1 | 1, mid + 1, r, u, v, d); st[id] = max(st[id << 1], st[id << 1 | 1]); } void update(int l, int r, int d) { d = d == -2 ? -MAX : d; update(1, 1, N, l, r, d); } int getMax(int l, int r) { int k = 31 - __builtin_clz(r - l + 1); return max(rmq[k][l], rmq[k][r - (1 << k) + 1]); } int solve(void) { for (int i = 1; i <= N; ++i) { update(i, +1); pp[i] = {i, i}; rmq[0][i] = K[i]; } for (int j = 1; (1 << j) <= N; ++j) { for (int i = 1; i + (1 << j) - 1 <= N; ++i) rmq[j][i] = max(rmq[j - 1][i], rmq[j - 1][i + (1 << j - 1)]); } for (int i = 1; i <= C; ++i) { int L = getPos(S[i]); ll[i] = pp[L].fi; int R = getPos(E[i]); rr[i] = pp[R].se; for (int j = E[i] - S[i]; j >= 1; --j) { update(getPos(S[i] + 1), -1); } pp[L] = {ll[i], rr[i]}; } int curPos = 1, curAns = 0; for (int i = 1; i <= C; ++i) { int maxValue = getMax(ll[i], rr[i] - 1); if (R < maxValue) update(ll[i], rr[i], -2); if (R > maxValue) update(ll[i], rr[i], +1); int id = 1, l = 1, r = N; while (l < r) { int mid = l + r >> 1; push(id); if (st[id << 1] == st[id]) id <<= 1, r = mid; else id = id << 1 | 1, l = mid + 1; } if (curAns < st[id]) { curAns = st[id]; curPos = l; } } return curPos; } int GetBestPosition(int _N, int _C, int _R, int *_K, int *_S, int *_E) { N = _N; C = _C; R = _R; for (int i = 1; i < N; ++i) { K[i] = _K[i - 1]; } for (int i = 1; i <= C; ++i) { S[i] = _S[i - 1]; E[i] = _E[i - 1]; } return solve() - 1; }

컴파일 시 표준 에러 (stderr) 메시지

tournament.cpp: In function 'void update(int, int, int, int, int, int)':
tournament.cpp:51:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     int mid = l + r >> 1; push(id);
      |               ~~^~~
tournament.cpp: In function 'int solve()':
tournament.cpp:75:67: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   75 |             rmq[j][i] = max(rmq[j - 1][i], rmq[j - 1][i + (1 << j - 1)]);
      |                                                                 ~~^~~
tournament.cpp:93:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |             int mid = l + r >> 1; push(id);
      |                       ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...