#include <cstdio> #include <cstdlib> #include <cmath> #include <vector> #include <algorithm> #include <utility> using namespace std; long long n, m; long long increases[500000]; long long increasesSums[500000]; struct Node { long long left; long long right; long long day; long long height; }; vector<Node> nodes; long long getSliceWithElement(long long element, long long left, long long right) { if (left >= right) { return left; } long long middle = (right + left) / 2; if (nodes[middle].left <= element && nodes[middle].right >= element) { return middle; }else if (nodes[middle].left > element) { return getSliceWithElement(element, left, middle-1); } else { return getSliceWithElement(element, middle+1, right); } } pair<long long, long long> getElementHeightWithSlice(long long element, long long day, long long height) { long long slice = getSliceWithElement(element, 0, nodes.size() - 1); long long dayDiff = day - nodes[slice].day; long long size = dayDiff * increases[element] + nodes[slice].height; pair<long long, long long> result; result.first = size; result.second = slice; return result; } pair<long long, long long> findFirstCutElement(long long day, long long height, long long left, long long right) { pair<long long, long long> result; pair<long long, long long> elementWithHeight; while (left < right) { long long middle = (right + left) / 2; elementWithHeight = getElementHeightWithSlice(middle, day, height); //first - size of area, second - slice id if (elementWithHeight.first >= height) { right = middle - 1; } else { left = middle + 1; } } elementWithHeight = getElementHeightWithSlice(left, day, height); result.second = elementWithHeight.second; result.first = elementWithHeight.first < height ? left : left-1; return result; } void calculateCut() { long long cutDay, cutHeight; scanf("%lld %lld", &cutDay, &cutHeight); pair<long long, long long> firstCutElement = findFirstCutElement(cutDay, cutHeight, 0, n - 1); //first - element, second - slice id if(firstCutElement.first >= n-1){ printf("%d\n", 0); return; } firstCutElement.first++; long long total = 0; long long borderElement = firstCutElement.first; long long originalBorderElement = borderElement; long long sliceId = firstCutElement.second; bool first = true; do { if (!first) { borderElement = nodes[sliceId].left; } first = false; long long dayDiff = cutDay - nodes[sliceId].day; total += increasesSums[nodes[sliceId].right] * dayDiff; total -= dayDiff * (borderElement > 0 ? increasesSums[borderElement - 1] : 0); total -= (cutHeight - nodes[sliceId].height) * (nodes[sliceId].right - borderElement + 1); } while (++sliceId < nodes.size()); printf("%lld\n", total); nodes.resize(firstCutElement.second + 1); Node nodeToAdd; nodeToAdd.left = originalBorderElement; nodeToAdd.right = n-1; nodeToAdd.day = cutDay; nodeToAdd.height = cutHeight; nodes[firstCutElement.second].right = originalBorderElement - 1; if (nodes[firstCutElement.second].right < nodes[firstCutElement.second].left) { nodes.pop_back(); } nodes.push_back(nodeToAdd); } int main() { scanf("%lld %lld", &n, &m); for (long long i = 0; i < n; ++i) { scanf("%lld", &(increases[i])); } sort(increases, increases + n); increasesSums[0] = increases[0]; for (long long i = 1; i < n; ++i) { increasesSums[i] = increasesSums[i - 1] + increases[i]; } Node node; node.left = 0; node.right = n - 1; node.day = 0; node.height = 0; nodes.push_back(node); for (long long i = 0; i < m; ++i) { calculateCut(); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 | #include <cstdio> #include <cstdlib> #include <cmath> #include <vector> #include <algorithm> #include <utility> using namespace std; long long n, m; long long increases[500000]; long long increasesSums[500000]; struct Node { long long left; long long right; long long day; long long height; }; vector<Node> nodes; long long getSliceWithElement(long long element, long long left, long long right) { if (left >= right) { return left; } long long middle = (right + left) / 2; if (nodes[middle].left <= element && nodes[middle].right >= element) { return middle; }else if (nodes[middle].left > element) { return getSliceWithElement(element, left, middle-1); } else { return getSliceWithElement(element, middle+1, right); } } pair<long long, long long> getElementHeightWithSlice(long long element, long long day, long long height) { long long slice = getSliceWithElement(element, 0, nodes.size() - 1); long long dayDiff = day - nodes[slice].day; long long size = dayDiff * increases[element] + nodes[slice].height; pair<long long, long long> result; result.first = size; result.second = slice; return result; } pair<long long, long long> findFirstCutElement(long long day, long long height, long long left, long long right) { pair<long long, long long> result; pair<long long, long long> elementWithHeight; while (left < right) { long long middle = (right + left) / 2; elementWithHeight = getElementHeightWithSlice(middle, day, height); //first - size of area, second - slice id if (elementWithHeight.first >= height) { right = middle - 1; } else { left = middle + 1; } } elementWithHeight = getElementHeightWithSlice(left, day, height); result.second = elementWithHeight.second; result.first = elementWithHeight.first < height ? left : left-1; return result; } void calculateCut() { long long cutDay, cutHeight; scanf("%lld %lld", &cutDay, &cutHeight); pair<long long, long long> firstCutElement = findFirstCutElement(cutDay, cutHeight, 0, n - 1); //first - element, second - slice id if(firstCutElement.first >= n-1){ printf("%d\n", 0); return; } firstCutElement.first++; long long total = 0; long long borderElement = firstCutElement.first; long long originalBorderElement = borderElement; long long sliceId = firstCutElement.second; bool first = true; do { if (!first) { borderElement = nodes[sliceId].left; } first = false; long long dayDiff = cutDay - nodes[sliceId].day; total += increasesSums[nodes[sliceId].right] * dayDiff; total -= dayDiff * (borderElement > 0 ? increasesSums[borderElement - 1] : 0); total -= (cutHeight - nodes[sliceId].height) * (nodes[sliceId].right - borderElement + 1); } while (++sliceId < nodes.size()); printf("%lld\n", total); nodes.resize(firstCutElement.second + 1); Node nodeToAdd; nodeToAdd.left = originalBorderElement; nodeToAdd.right = n-1; nodeToAdd.day = cutDay; nodeToAdd.height = cutHeight; nodes[firstCutElement.second].right = originalBorderElement - 1; if (nodes[firstCutElement.second].right < nodes[firstCutElement.second].left) { nodes.pop_back(); } nodes.push_back(nodeToAdd); } int main() { scanf("%lld %lld", &n, &m); for (long long i = 0; i < n; ++i) { scanf("%lld", &(increases[i])); } sort(increases, increases + n); increasesSums[0] = increases[0]; for (long long i = 1; i < n; ++i) { increasesSums[i] = increasesSums[i - 1] + increases[i]; } Node node; node.left = 0; node.right = n - 1; node.day = 0; node.height = 0; nodes.push_back(node); for (long long i = 0; i < m; ++i) { calculateCut(); } } |