Submission #927748

#TimeUsernameProblemLanguageResultExecution timeMemory
927748boris_mihovTwo Dishes (JOI19_dishes)C++17
10 / 100
10045 ms131328 KiB
#include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <vector> #define int long long typedef long long llong; const int MAXN = 1000000 + 10; const int MAXLOG = 20; const llong INF = 1e18; int n, m; template <typename T> struct Fenwick { T tree[MAXN]; void update(int pos, T val) { for (int idx = pos ; idx <= m ; idx += idx & (-idx)) { tree[idx] += val; } } T query(int pos) { T res = 0; for (int idx = pos ; idx > 0 ; idx -= idx & (-idx)) { res += tree[idx]; } return res; } int findKthZero(int k) { int idx = 0; for (int log = MAXLOG - 1 ; log >= 0 ; --log) { if (idx + (1 << log) <= m && (1 << log) - tree[idx + (1 << log)] < k) { idx += (1 << log); k -= (1 << log) - tree[idx]; } } return idx + 1; } int findKthOne(int k) { int idx = 0; for (int log = MAXLOG - 1 ; log >= 0 ; --log) { if (idx + (1 << log) <= m && tree[idx + (1 << log)] < k) { idx += (1 << log); k -= tree[idx]; } } return idx + 1; } }; struct SegmentTree { struct Node { llong value; llong lazy; Node() { value = lazy; } }; Node tree[4*MAXN]; void push(int node, int l, int r) { if (tree[node].lazy == 0) { return; } tree[node].value += tree[node].lazy; if (l < r) { tree[2*node].lazy += tree[node].lazy; tree[2*node + 1].lazy += tree[node].lazy; } tree[node].lazy = 0; } void rangeUpdate(int l, int r, int node, int queryL, int queryR, int queryVal) { push(node, l, r); if (queryR < l || r < queryL) { return; } if (queryL <= l && r <= queryR) { tree[node].lazy = queryVal; push(node, l, r); return; } int mid = (l + r) / 2; rangeUpdate(l, mid, 2*node, queryL, queryR, queryVal); rangeUpdate(mid + 1, r, 2*node + 1, queryL, queryR, queryVal); } void setUpdate(int l, int r, int node, int queryPos, llong queryVal) { push(node, l, r); if (queryPos < l || r < queryPos) { return; } if (l == r) { tree[node].value = queryVal; return; } int mid = (l + r) / 2; setUpdate(l, mid, 2*node, queryPos, queryVal); setUpdate(mid + 1, r, 2*node + 1, queryPos, queryVal); } llong query(int l, int r, int node, int queryPos) { push(node, l, r); if (l == r) { return tree[node].value; } int mid = (l + r) / 2; if (queryPos <= mid) return query(l, mid, 2*node, queryPos); else return query(mid + 1, r, 2*node + 1, queryPos); } void update(int pos, llong value) { setUpdate(1, m + 1, 1, pos, value); } void rangeUpdate(int l, int r, int value) { rangeUpdate(1, m + 1, 1, l, r, value); } llong query(int pos) { return query(1, m + 1, 1, pos); } }; Fenwick <int> fenwickNext; Fenwick <llong> fenwickActive; SegmentTree dp; struct Dish { int time; llong limit; int reward; int idx; bool type; }; Dish a[MAXN]; Dish b[MAXN]; llong prefixA[MAXN]; llong prefixB[MAXN]; bool isNext[MAXN]; bool isActive[MAXN]; llong dpBorderM[MAXN]; int globalRow; llong findValue(int col) { if (col == m + 1) { return dp.query(m + 1); } int cnt = col - 1 - fenwickNext.query(col - 1); int pos = m; if (cnt != m - fenwickNext.query(m)) { // std::cout << "IN THE FUCKING IF: " << cnt << ' ' << m << ' ' << fenwickNext.query(m) << '\n'; // std::cout << "next is\n"; // for (int i = 1 ; i <= m ; ++i) // { // std::cout << fenwickNext.query(i) - fenwickNext.query(i - 1); // } // std::cout << '\n'; // std::cout << "lapai\n"; pos = fenwickNext.findKthZero(cnt + 1); } // if (col == 3) std::cout << "\n\n value: " << col << ' ' << m - fenwickNext.query(m) << ' ' << cnt << ' ' << pos << ' ' << fenwickActive.query(pos - 1) - fenwickActive.query(col - 1) + dp[pos] << '\n'; return fenwickActive.query(pos - 1) - fenwickActive.query(col - 1) + dp.query(pos); } void fix(int col) { // std::cout << "fix: " << col << '\n'; assert(col <= m); llong prevVal = findValue(col); llong curr = dp.query(col); llong next = findValue(col + 1) + fenwickActive.query(col) - fenwickActive.query(col - 1); // std::cout << "here: " << curr << ' ' << next << '\n'; int res = fenwickNext.query(col) - fenwickNext.query(col - 1); fenwickNext.update(col, -res); int nextVal = 0; if (curr > next) { fenwickNext.update(col, 0); // unessesary } else { nextVal = 1; fenwickNext.update(col, 1); } // std::cout << "set: " << col << " = " << curr << ' ' << next << '\n'; dp.update(col, std::max(curr, next)); if (col > 1) { // fix(col - 1); if (fenwickNext.query(col - 1) < col - 1) { int cntZeroesToNow = col - 1 - fenwickNext.query(col - 1); int pos = fenwickNext.findKthZero(cntZeroesToNow); llong nextVal = findValue(pos + 1) + fenwickActive.query(pos) - fenwickActive.query(pos - 1); if (nextVal > dp.query(pos)) fix(pos); } if (fenwickNext.query(col - 1) > 0) { int cntOnesToNow = fenwickNext.query(col - 1); int pos = fenwickNext.findKthOne(cntOnesToNow); llong nextVal = findValue(pos + 1) + fenwickActive.query(pos) - fenwickActive.query(pos - 1); if (nextVal > dp.query(pos)) fix(pos); } // if (prevVal <= dp[col]) // { // int cntBefore = col - 1 - fenwickNext.query(col - 1); // for (int idx = col - 1 ; idx >= 1 ; --idx) // { // if (fenwickNext.query(idx) - fenwickNext.query(idx - 1) == 0) // { // fix(idx); // return; // } // llong val = findValue(idx); // fix(idx); // llong val2 = findValue(idx); // if (val != val2) // { // assert(fenwickNext.query(idx) - fenwickNext.query(idx - 1) == 0); // exit(0); // } // assert(val == val2); // } // // std::cout << "cnt before: " << cntBefore << '\n'; // // if (cntBefore > 0) // // { // // fix(fenwickNext.findKthZero(cntBefore)); // // } // } else // { // // assert(false); // int cntBefore = fenwickNext.query(col - 1); // // std::cout << "cnt before: " << cntBefore << '\n'; // if (cntBefore > 0) // { // fix(fenwickNext.findKthOne(cntBefore)); // } // } } } void applyUpdate(int to, int val) { dp.rangeUpdate(1, to, val); } std::vector <int> activateAt[MAXN]; void solve() { for (int i = 1 ; i <= n ; ++i) { prefixA[i] = prefixA[i - 1] + a[i].time; } for (int i = 1 ; i <= m ; ++i) { prefixB[i] = prefixB[i - 1] + b[i].time; } for (int aPos = n ; aPos >= 1 ; --aPos) { dpBorderM[aPos] = dpBorderM[aPos + 1] + (prefixA[aPos - 1] + prefixB[m] + a[aPos].time <= a[aPos].limit ? a[aPos].reward : 0); } for (int i = 1 ; i <= m ; ++i) { int l = 0, r = n + 2, mid; while (l < r - 1) { mid = (l + r) / 2; if (prefixA[mid - 1] + prefixB[i] <= b[i].limit) l = mid; else r = mid; } activateAt[l].push_back(i); // std::cout << "here: " << i << ' ' << l << '\n'; } globalRow = n + 1; for (int i = 1 ; i <= n ; ++i) { fenwickNext.update(i, 1); isNext[i] = true; } std::sort(activateAt[n + 1].begin(), activateAt[n + 1].end(), std::greater <int> ()); for (const int &idx : activateAt[globalRow]) { // std::cout << "activate: " << idx << '\n'; fenwickActive.update(idx, b[idx].reward); fix(idx); } // std::cout << "dp after: " << n + 1 << '\n'; // for (int i = 1 ; i <= m ; ++i) // { // std::cout << findValue(i) << ' '; // } // std::cout << '\n'; for (globalRow = n ; globalRow >= 1 ; --globalRow) { // std::cout << " global: " << globalRow << '\n'; for (const int &idx : activateAt[globalRow]) { dp.update(idx, findValue(idx)); } int l = 0, r = m + 1, mid; while (l < r - 1) { mid = (l + r) / 2; if (prefixA[globalRow] + prefixB[mid - 1] <= a[globalRow].limit) l = mid; else r = mid; } if (l > 0) { dp.update(l, findValue(l)); } for (const int &idx : activateAt[globalRow]) { // std::cout << " activate: " << idx << '\n'; fenwickActive.update(idx, b[idx].reward); } if (l > 0) activateAt[globalRow].push_back(l); applyUpdate(l, a[globalRow].reward); dp.update(m + 1, dpBorderM[globalRow]); activateAt[globalRow].push_back(m); std::sort(activateAt[globalRow].begin(), activateAt[globalRow].end(), std::greater <int> ()); // std::cout << "after applying\n"; // for (int i = 1 ; i <= m ; ++i) // { // std::cout << findValue(i) << ' '; // } // std::cout << '\n'; // std::cout << "next is\n"; // for (int i = 1 ; i <= m ; ++i) // { // std::cout << fenwickNext.query(i) - fenwickNext.query(i - 1); // } // std::cout << '\n'; for (const int &idx : activateAt[globalRow]) { // std::cout << "fix: " << idx << '\n'; fix(idx); // if (idx > 1) fix(idx - 1); } // for (int idx = m ; idx >= 1 ; --idx) // { // fix(idx); // } // std::cout << "dp after: " << globalRow << '\n'; // for (int i = 1 ; i <= m ; ++i) // { // std::cout << findValue(i) << ' '; // } // std::cout << '\n'; // std::cout << "active\n"; // for (int i = 1 ; i <= m ; ++i) // { // std::cout << isActive[i] << ' '; // } // std::cout << '\n'; // std::cout << "next\n"; // for (int i = 1 ; i <= m ; ++i) // { // std::cout << isNext[i] << ' '; // } // std::cout << '\n'; } globalRow++; std::cout << findValue(1) << '\n'; } void input() { std::cin >> n >> m; for (int i = 1 ; i <= n ; ++i) { std::cin >> a[i].time >> a[i].limit >> a[i].reward; a[i].idx = i; a[i].type = false; } for (int i = 1 ; i <= m ; ++i) { std::cin >> b[i].time >> b[i].limit >> b[i].reward; b[i].idx = i; a[i].type = true; } } void fastIOI() { std::ios_base :: sync_with_stdio(0); std::cout.tie(nullptr); std::cin.tie(nullptr); } signed main() { fastIOI(); input(); solve(); return 0; }

Compilation message (stderr)

dishes.cpp: In function 'void fix(long long int)':
dishes.cpp:222:11: warning: unused variable 'prevVal' [-Wunused-variable]
  222 |     llong prevVal = findValue(col);
      |           ^~~~~~~
dishes.cpp:229:9: warning: variable 'nextVal' set but not used [-Wunused-but-set-variable]
  229 |     int nextVal = 0;
      |         ^~~~~~~
dishes.cpp: In constructor 'SegmentTree::Node::Node()':
dishes.cpp:77:21: warning: '*<unknown>.SegmentTree::Node::lazy' is used uninitialized in this function [-Wuninitialized]
   77 |             value = lazy;
      |                     ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...