제출 #1075283

#제출 시각아이디문제언어결과실행 시간메모리
1075283skittles1412팀들 (IOI15_teams)C++17
34 / 100
4061 ms158652 KiB
#include "bits/extc++.h" using namespace std; template <typename T, typename... U> void dbgh(const T& t, const U&... u) { cerr << t; ((cerr << " | " << u), ...); cerr << endl; } #ifdef DEBUG #define dbg(...) \ cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \ dbgh(__VA_ARGS__) #else #define dbg(...) #define cerr \ if (false) \ cerr #endif using ll = long long; #define endl "\n" #define long int64_t #define sz(x) int(std::size(x)) inline void init_io() { cin.tie(nullptr); cin.exceptions(ios::failbit); ios_base::sync_with_stdio(false); } template <typename T> ostream& operator<<(ostream& out, const vector<T>& arr) { out << "["; for (int i = 0; i < sz(arr); i++) { if (i) { out << ", "; } out << arr[i]; } return out << "]"; } template <typename T> struct PSA { int n; vector<T> psum; template <typename U> PSA(const vector<U>& arr) : n(sz(arr)), psum(n + 1) { for (int i = 0; i < n; i++) { psum[i + 1] = psum[i] + arr[i]; } } T query(int l, int r) const { return psum[r] - psum[l]; } }; template <typename T> bool on(T mask, int bit) { return (mask >> bit) & 1; } template <typename T> vector<T> iota(int n, T x) { vector<T> arr(n); iota(begin(arr), end(arr), x); return arr; } template <typename T> T reversed(T arr) { reverse(begin(arr), end(arr)); return arr; } template <typename A, typename B> ostream& operator<<(ostream& out, const pair<A, B>& p) { return out << "(" << p.first << ", " << p.second << ")"; } namespace st1 { struct Node { int lc, rc, v; } heap[(500 << 20) / sizeof(Node)]; int n, hind = 1; void update(int& o, int l, int r, int ind, int x) { heap[hind] = heap[o]; o = hind++; if (l == r) { heap[o].v += x; return; } int mid = (l + r) / 2; if (ind <= mid) { update(heap[o].lc, l, mid, ind, x); } else { update(heap[o].rc, mid + 1, r, ind, x); } heap[o].v = heap[heap[o].lc].v + heap[heap[o].rc].v; } void update(int& root, int ind, int x) { update(root, 0, n - 1, ind, x); } int query_pref(int o, int qr) { int ans = 0, l = 0, r = n - 1; while (true) { if (!o) { return ans; } else if (r <= qr) { return ans + heap[o].v; } int mid = (l + r) / 2; if (qr <= mid) { o = heap[o].lc; r = mid; } else { ans += heap[heap[o].lc].v; l = mid + 1; o = heap[o].rc; } } } } // namespace st1 struct Solver { int n; vector<pair<int, int>> arr; vector<int> roots; Solver() {} Solver(const vector<pair<int, int>>& arr) : n(sz(arr)), arr(arr), roots(n + 1) { st1::n = n + 5; vector<vector<int>> evts(n + 1); for (auto& [l, r] : arr) { evts[r].push_back(l); } int root = 0; for (int i = n; i >= 0; i--) { for (auto& a : evts[i]) { st1::update(root, a, +1); } roots[i] = root; } } bool query2(vector<pair<int, int>> carr) { carr.insert(begin(carr), pair {-1, 0}); int m = sz(carr); vector cnt(m, vector(m, 0)); // int cnt[m][m] {}; { int comp1[n + 1], comp2[n + 1]; for (int i = 0, j = 0; i <= n; i++) { while (j + 1 < m && carr[j + 1].first < i) { j++; } comp1[i] = j; } for (int i = 0, j = 0; i <= n; i++) { while (j + 1 < m && carr[j + 1].first <= i) { j++; } comp2[i] = j; } dbg(vector(comp1, comp1 + n + 1)); dbg(vector(comp2, comp2 + n + 1)); for (auto& [l, r] : arr) { dbg(comp1[l], comp2[r]); cnt[comp1[l]][comp2[r]]++; } } dbg(cnt); vector va(m, vector(m + 1, 0)); for (int i = 1; i < m; i++) { for (int j = m - 1; j >= 0; j--) { va[i][j] = va[i - 1][j] + va[i][j + 1] - va[i - 1][j + 1] + cnt[i - 1][j]; } } auto querya = [&](int x, int y) -> int { return va[x][y]; int ans = 0; for (int i = 0; i < x; i++) { for (int j = y; j < m; j++) { ans += cnt[i][j]; } } return ans; }; auto query2 = [&](int il, int ir) -> int { return querya(ir, ir) - querya(il, ir); int ans = 0; for (int i = il; i < ir; i++) { for (int j = ir; j < m; j++) { ans += cnt[i][j]; } } return ans; }; vector dp(m, 0); for (int i = m - 1; i >= 0; i--) { for (int j = i + 1; j < m; j++) { dp[i] = min(dp[i], va[j][j] - va[i][j] + dp[j] - carr[j].second); } } return dp[0] >= 0; } bool query(vector<int> qarr) { if (accumulate(begin(qarr), end(qarr), long(0)) > n) { return false; } vector<pair<int, int>> carr; sort(begin(qarr), end(qarr)); for (int i = 0; i < sz(qarr);) { int cl = i; for (; i < sz(qarr) && qarr[cl] == qarr[i]; i++) ; carr.emplace_back(qarr[cl], (i - cl) * qarr[cl]); } if (sz(carr) > 400 || true) { return query2(carr); } carr.insert(begin(carr), pair {-1, 0}); int m = sz(carr); vector dp(m, 0); for (int j = m - 1; j >= 1; j--) { int qr = carr[j].first, cv = st1::query_pref(roots[qr], qr); for (int i = 0; i < j; i++) { dp[i] = min(dp[i], cv - st1::query_pref(roots[qr], carr[i].first) + dp[j] - carr[j].second); } } return dp[0] >= 0; } } solver; void init(int n, int arra[], int arrb[]) { solver = Solver([&]() { vector<pair<int, int>> cv; for (int i = 0; i < n; i++) { cv.emplace_back(arra[i], arrb[i]); } return cv; }()); } int can(int m, int arr[]) { return solver.query(vector(arr, arr + m)); }

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

teams.cpp: In constructor 'Solver::Solver(const std::vector<std::pair<int, int> >&)':
teams.cpp:146:42: warning: declaration of 'arr' shadows a member of 'Solver' [-Wshadow]
  146 |     Solver(const vector<pair<int, int>>& arr)
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:142:28: note: shadowed declaration is here
  142 |     vector<pair<int, int>> arr;
      |                            ^~~
teams.cpp: In constructor 'Solver::Solver(const std::vector<std::pair<int, int> >&)':
teams.cpp:146:42: warning: declaration of 'arr' shadows a member of 'Solver' [-Wshadow]
  146 |     Solver(const vector<pair<int, int>>& arr)
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:142:28: note: shadowed declaration is here
  142 |     vector<pair<int, int>> arr;
      |                            ^~~
teams.cpp: In constructor 'Solver::Solver(const std::vector<std::pair<int, int> >&)':
teams.cpp:146:42: warning: declaration of 'arr' shadows a member of 'Solver' [-Wshadow]
  146 |     Solver(const vector<pair<int, int>>& arr)
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:142:28: note: shadowed declaration is here
  142 |     vector<pair<int, int>> arr;
      |                            ^~~
teams.cpp: In member function 'bool Solver::query2(std::vector<std::pair<int, int> >)':
teams.cpp:215:14: warning: variable 'query2' set but not used [-Wunused-but-set-variable]
  215 |         auto query2 = [&](int il, int ir) -> int {
      |              ^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...