Submission #1243322

#TimeUsernameProblemLanguageResultExecution timeMemory
1243322nibertDistributing Candies (IOI21_candies)C++20
38 / 100
352 ms27808 KiB
#include <vector> #include <algorithm> using namespace std; struct SegTree { struct Node { long long mn, mx; long long lazy; Node(long long _mn, long long _mx, long long _lazy) : mn(_mn), mx(_mx), lazy(_lazy) {} }; int cap; vector<Node> tree; SegTree(int n, int _cap) : cap(_cap), tree(4 * n + 1, {0, 0, 0}) {} inline void apply(int pos, int val) { tree[pos].mn += val; tree[pos].mx += val; tree[pos].lazy += val; } inline void push(int pos) { long long val = tree[pos].lazy; if (val != 0) { apply(pos * 2 + 1, val); apply(pos * 2 + 2, val); tree[pos].lazy = 0; } } inline void merge(int pos) { int lChild = 2 * pos + 1, rChild = 2 * pos + 2; tree[pos].mn = min(tree[lChild].mn, tree[rChild].mn); tree[pos].mx = max(tree[lChild].mx, tree[rChild].mx); } inline void update(int tPos, int tLeft, int tRight, int l, int r, int val) { if (l > tRight || tLeft > r) { return; } if (l <= tLeft && tRight <= r) { apply(tPos, val); return; } push(tPos); int tMid = tLeft + (tRight - tLeft) / 2; update(tPos * 2 + 1, tLeft, tMid, l, min(tMid, r), val); update(tPos * 2 + 2, tMid + 1, tRight, max(l, tMid + 1), r, val); merge(tPos); } inline void fixLeftBound(int tPos, int tLeft, int tRight) { if (tree[tPos].mn >= 0) { return; } if (tree[tPos].mx < 0) { apply(tPos, -tree[tPos].mx); } if (tLeft == tRight) { return; } push(tPos); int tMid = tLeft + (tRight - tLeft) / 2; fixLeftBound(tPos * 2 + 1, tLeft, tMid); fixLeftBound(tPos * 2 + 2, tMid + 1, tRight); merge(tPos); } inline void fixRgihtBound(int tPos, int tLeft, int tRight) { if (tree[tPos].mx <= cap) { return; } if (tree[tPos].mn > cap) { apply(tPos, cap - tree[tPos].mn); } if (tLeft == tRight) { return; } push(tPos); int tMid = tLeft + (tRight - tLeft) / 2; fixRgihtBound(tPos * 2 + 1, tLeft, tMid); fixRgihtBound(tPos * 2 + 2, tMid + 1, tRight); merge(tPos); } inline int get(int tPos, int tLeft, int tRight, int pos) { if (tLeft == tRight) { return tree[tPos].mn; } push(tPos); int tMid = tLeft + (tRight - tLeft) / 2; if (pos <= tMid) { return get(tPos * 2 + 1, tLeft, tMid, pos); } return get(tPos * 2 + 2, tMid + 1, tRight, pos); } }; vector<int> distribute_candies(vector<int> c,vector<int> l,vector<int> r,vector<int> v) { int n = c.size(), q = r.size(); vector<long long> boxes(n, 0); bool isSubtask1 = (n <= 2000 && q <= 2000); bool isSubtask2 = true; for (int i = 0; i < q; ++i) if (v[i] <= 0) isSubtask2 = false; bool isSubtask3 = true; for (int i = 1; i < n; ++i) if (c[i] != c[0]) isSubtask3 = false; if(isSubtask1) { for (int i = 0; i < q; i++) { int left = l[i], right = r[i], value = v[i]; if (value > 0) { for (int j = left; j <= right; j++) { boxes[j] = min(1LL * c[j], boxes[j] + value); } } else { for (int j = left; j <= right; j++) { boxes[j] = max(0ll, boxes[j] + value); } } } vector<int> result(n); for (int i=0; i < n; i ++){ result[i] = boxes[i]; } return result; } else if(isSubtask2) { for (int i = 0; i < q; i++){ int left = l[i], right = r[i], value = v[i]; boxes[left] += value; if (right + 1 < n) { boxes[right + 1] -= value; } } for (int i = 1; i < n; i++){ boxes[i] += boxes[i - 1]; boxes[i-1] = min(1LL * c[i-1], boxes[i - 1]); } boxes[n - 1] = min(1LL * c[n - 1], boxes[n - 1]); vector<int> result(n); for (int i=0; i < n; i ++){ result[i] = boxes[i]; } return result; } else if(isSubtask3) { SegTree segTree(n, c[0]); for (int i = 0; i < q; i++) { segTree.update(0, 0, n - 1, l[i], r[i], v[i]); segTree.fixLeftBound(0, 0, n - 1); segTree.fixRgihtBound(0, 0, n - 1); } vector<int> res(n); for (int i = 0; i < n; i++) { res[i] = segTree.get(0, 0, n - 1, i); } return res; } }

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:160:1: warning: control reaches end of non-void function [-Wreturn-type]
  160 | }
      | ^
#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...