제출 #1075277

#제출 시각아이디문제언어결과실행 시간메모리
1075277skittles1412팀들 (IOI15_teams)C++17
77 / 100
4034 ms155496 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(int o, int l, int r, int ql, int qr) { if (!o) { return 0; } else if (ql <= l && r <= qr) { return heap[o].v; } int mid = (l + r) / 2, ans = 0; if (ql <= mid) { ans += query(heap[o].lc, l, mid, ql, qr); } if (mid < qr) { ans += query(heap[o].rc, mid + 1, r, ql, qr); } return ans; } int query(int root, int l, int r) { return query(root, 0, n - 1, l, r); } } // namespace st1 // int main() { // st1::n = 100; // // int root = 0; // st1::update(root, 1, +1); // st1::update(root, 4, +1); // dbg(st1::query(root, 1, 10)); // } 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 query(const vector<int>& qarr) { auto query2 = [&](int ql, int qr) -> int { return st1::query(roots[qr], ql + 1, qr); // int ans = 0; // // for (auto& [l, r] : arr) { // ans += ql < l && l <= qr && qr <= r; // } // // return ans; }; map<int, int> cc_mp; for (auto& a : qarr) { cc_mp[a] += a; } vector<pair<int, int>> carr(begin(cc_mp), end(cc_mp)); carr.insert(begin(carr), pair {-1, 0}); int m = sz(carr); 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], query2(carr[i].first, carr[j].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:155:42: warning: declaration of 'arr' shadows a member of 'Solver' [-Wshadow]
  155 |     Solver(const vector<pair<int, int>>& arr)
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:151:28: note: shadowed declaration is here
  151 |     vector<pair<int, int>> arr;
      |                            ^~~
teams.cpp: In constructor 'Solver::Solver(const std::vector<std::pair<int, int> >&)':
teams.cpp:155:42: warning: declaration of 'arr' shadows a member of 'Solver' [-Wshadow]
  155 |     Solver(const vector<pair<int, int>>& arr)
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:151:28: note: shadowed declaration is here
  151 |     vector<pair<int, int>> arr;
      |                            ^~~
teams.cpp: In constructor 'Solver::Solver(const std::vector<std::pair<int, int> >&)':
teams.cpp:155:42: warning: declaration of 'arr' shadows a member of 'Solver' [-Wshadow]
  155 |     Solver(const vector<pair<int, int>>& arr)
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:151:28: note: shadowed declaration is here
  151 |     vector<pair<int, int>> arr;
      |                            ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...