제출 #103799

#제출 시각아이디문제언어결과실행 시간메모리
103799alexpetrescu마상시합 토너먼트 (IOI12_tournament)C++14
49 / 100
156 ms5260 KiB
#include <algorithm> #define MAXN 100009 #define MAXP 265000 int aint[MAXP], t[MAXN]; int val[MAXN], v[MAXN], calc[MAXN]; int best[MAXN], l[MAXN], r[MAXN]; int N, R, rez, left, right, cnt, poz; void dfs(int p, int st, int dr) { aint[p] = dr - st + 1; if (st < dr) { int m = (st + dr) / 2; dfs(2 * p, st, m); dfs(2 * p + 1, m + 1, dr); } } void update(int p, int st, int dr) { if (st == dr) aint[p] = val[st] != -1; else { int m = (st + dr) / 2; if (poz <= m) update(2 * p, st, m); else update(2 * p + 1, m + 1, dr); aint[p] = aint[2 * p] + aint[2 * p + 1]; } } void query(int p, int st, int dr) { if (st == dr) poz = st; else { int m = (st + dr) / 2; if (cnt <= aint[2 * p]) query(2 * p, st, m); else { cnt -= aint[2 * p]; query(2 * p + 1, m + 1, dr); } } } void DFS(int p, int st, int dr) { if (st == dr) aint[p] = v[st]; else { int m = (st + dr) / 2; DFS(2 * p, st, m); DFS(2 * p + 1, m + 1, dr); aint[p] = std::max(aint[2 * p], aint[2 * p + 1]); } } void UPDATE(int p, int st, int dr) { if (st == dr) aint[p] = v[st]; else { int m = (st + dr) / 2; if (left <= m) UPDATE(2 * p, st, m); if (m < right) UPDATE(2 * p + 1, m + 1, dr); aint[p] = std::max(aint[2 * p], aint[2 * p + 1]); } } void QUERY(int p, int st, int dr) { if (left <= st && dr <= right) rez = std::max(rez, aint[p]); else { int m = (st + dr) / 2; if (left <= m) QUERY(2 * p, st, m); if (m < right) QUERY(2 * p + 1, m + 1, dr); } } void solve(int x) { rez = -1; left = l[x]; right = r[x]; QUERY(1, 0, N - 1); if (best[x] == rez) return ; best[x] = rez; if (t[x] != -1) solve(t[x]); if (best[x] == R) { calc[x] = 1; if (t[x] != -1) calc[x] += calc[t[x]]; } else calc[x] = 0; } int GetBestPosition(int ceecunumarulasta, int C, int darcuastalalaltcei, int *K, int *S, int *E) { N = ceecunumarulasta; R = darcuastalalaltcei; for (int i = 0; i < N; i++) val[i] = i, l[i] = i, r[i] = i; dfs(1, 0, N - 1); for (int i = 0; i < N + C; i++) t[i] = -1; for (int i = 0; i < C; i++) { cnt = S[i] + 1; query(1, 0, N - 1); int pos = poz; l[i + N] = l[val[poz]]; t[val[poz]] = i + N; val[poz] = -1; update(1, 0, N - 1); int u = E[i] - S[i]; while (u > 0) { u--; cnt = S[i] + 1; query(1, 0, N - 1); t[val[poz]] = i + N; r[i + N] = r[val[poz]]; val[poz] = -1; update(1, 0, N - 1); } val[poz] = i + N; update(1, 0, N - 1); } for (int i = 0; i < N - 1; i++) v[i] = K[i]; v[N - 1] = R; DFS(1, 0, N - 1); for (int i = C + N - 1; i >= 0; i--) { rez = -1; left = l[i]; right = r[i]; QUERY(1, 0, N - 1); best[i] = rez; if (best[i] == R) { calc[i] = 1; if (t[i] != -1) calc[i] += calc[t[i]]; } } int ans = calc[N - 1], sol = N - 1; for (int i = N - 2; i >= 0; i--) { v[i + 1] = v[i]; v[i] = R; left = i; right = i + 1; UPDATE(1, 0, N - 1); solve(i + 1); solve(i); if (calc[i] >= ans) ans = calc[i], sol = i; } return sol; }

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

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:110:13: warning: unused variable 'pos' [-Wunused-variable]
         int pos = poz;
             ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...