제출 #429165

#제출 시각아이디문제언어결과실행 시간메모리
429165timmyfeng팀들 (IOI15_teams)C++17
100 / 100
1459 ms207264 KiB
#include <bits/stdc++.h> using namespace std; const int N = 500001, S = 64 * N; int sum[S], child[S][2], ptr = 1; int segtree(int x) { child[ptr][0] = child[ptr][1] = 0; sum[ptr] = x; return ptr++; } int segtree(int l, int r) { child[ptr][0] = l, child[ptr][1] = r; sum[ptr] = sum[l] + sum[r]; return ptr++; } int build(int l, int r) { int u = segtree(0); if (l < r) { int m = (l + r) / 2; child[u][0] = build(l, m); child[u][1] = build(m + 1, r); } return u; } int update(int u, int a, int x, int l, int r) { if (l == r) { return segtree(sum[u] + x); } else { int m = (l + r) / 2; if (a <= m) { return segtree(update(child[u][0], a, x, l, m), child[u][1]); } else { return segtree(child[u][0], update(child[u][1], a, x, m + 1, r)); } } } int copy(int u, int v, int a, int b, int l, int r) { if (b < a || b < l || r < a) { return v; } else if (a <= l && r <= b) { return u; } else { int m = (l + r) / 2; return segtree( copy(child[u][0], child[v][0], a, b, l, m), copy(child[u][1], child[v][1], a, b, m + 1, r) ); } } int assign(int u, int v, int &k) { if (child[v][0] == 0) { int delta = min(k, sum[u] - sum[v]); k -= delta; return segtree(sum[v] + delta); } else if (sum[u] - sum[v] <= k) { k -= sum[u] - sum[v]; return u; } else { int l = assign(child[u][0], child[v][0], k); int r = k > 0 ? assign(child[u][1], child[v][1], k) : child[v][1]; return segtree(l, r); } } int root[N], n; void init(int n, int a[], int b[]) { ::n = n; vector<array<int, 2>> students; for (int i = 0; i < n; ++i) { students.push_back({a[i], b[i]}); } sort(students.begin(), students.end()); root[0] = build(1, n); for (int i = 1, j = 0; i <= n; ++i) { root[i] = root[i - 1]; while (j < n && students[j][0] == i) { root[i] = update(root[i], students[j++][1], 1, 1, n); } } } bool can(int m, int k[]) { int temp = ptr; sort(k, k + m); int used = root[0]; for (int i = 0; i < m; ++i) { used = copy(root[k[i]], used, 1, k[i] - 1, 1, n); used = assign(root[k[i]], used, k[i]); if (k[i] > 0) { return false; } } ptr = temp; return true; }

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

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:74:15: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   74 | void init(int n, int a[], int b[]) {
      |           ~~~~^
teams.cpp:72:14: note: shadowed declaration is here
   72 | int root[N], n;
      |              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...