// Potyczki Algorytmiczne 2015 // runda 1 // SIAno // Tomasz Pastusiak #include <iostream> #include <algorithm> #include <functional> #include <stack> using namespace std; #define MAX_M_N 500000 //#define MAX_M_N 5 //#define MAX_M_N 4 long long int growthSpeed[MAX_M_N]; long long int cutDays[MAX_M_N + 1]; // place for fake 0 height cut at day 0 long long int cutHeights[MAX_M_N + 1]; // place for fake 0 height cut at day 0 long long int cutAreas[MAX_M_N + 1]; // place for fake 0 height cut at day 0 long long int areaGrowth[MAX_M_N + 1]; // total growth on area 0..(i-1) long long int totalWeights[MAX_M_N + 2]; // total weight cut grass after i'th cut (0 cuts give 0 grass), additional +1 for fake cut // entries in the tree numbered from 1 to 2*n - 1 // base elements have numbers: n + 0 ..... n + n - 1 // information is stored on areas ( log(n) ) // information is retrieved from points by traversing to the root ( log(n) ) class AreaHeightDateTree{ public: long long int heightTree[MAX_M_N*2]; long long int dateTree[MAX_M_N*2]; long long int n; long long int size; void setSize(long long int n){ this->n = n; size = 2*n; for(long long int i=1;i<size;++i){ heightTree[i] = 0; // grass height at time 0 = 0 dateTree[i] = 0; } } long long int getHeight(long long int position, long long int currentDate){ long long int node = n + position; long long int storedHeight = heightTree[node]; long long int storedDate = dateTree[node]; while (node != 1) { node /= 2; if(dateTree[node] > storedDate){ storedHeight = heightTree[node]; storedDate = dateTree[node]; } } long long int currentHeight = storedHeight + (currentDate - storedDate)*(long long int)growthSpeed[position]; return currentHeight; } // get current height at position void setAreaHeight(long long int areaFrom, long long int areaTo, long long int height, long long int currentDate){ long long int nl = n + areaFrom, nr = n + areaTo; // node left, node right heightTree[nl] = heightTree[nr] = height; dateTree[nl] = dateTree[nr] = currentDate; while (nl / 2 != nr / 2) { if (nl % 2 == 0){ heightTree[nl + 1] = height; dateTree[nl + 1] = currentDate; } // if left node is left child of some parent, save info in right brother if (nr % 2 == 1){ heightTree[nr - 1] = height; dateTree[nr - 1] = currentDate; } // if right node is right child of some parent, save info in left brother nl /= 2; nr /= 2; } } long long int getAreaHigherThan(long long int height, long long int currentDate){ // use binary search long long int l = 0, r = n, mid; while(l != r){ mid = (l + r)/2; long long int midHeight = getHeight(mid, currentDate); if(midHeight > height) l = mid + 1; else r = mid; } return l; // or r } // get Area higher than }; AreaHeightDateTree ahdt; int main(){ ios_base::sync_with_stdio(false); long long int n, m; cin >> n >> m; for(long long int i=0; i<n ;++i){ cin >> growthSpeed[i]; } for(long long int i=0; i<m; ++i){ cin >> cutDays[i] >> cutHeights[i]; } // DATA LOADED // for algorithm to work, growthSpeed has to be sorted sort(growthSpeed, growthSpeed + n, greater<long long int>()); areaGrowth[0] = 0; // area of size 0 do not grow at all for(long long int i=0; i<n ;++i){ areaGrowth[i + 1] = areaGrowth[i] + growthSpeed[i]; } ahdt.setSize(n); // lets calculate cut areas using AreaHeightDateTree for(long long int i=0; i<m; ++i){ cutAreas[i] = ahdt.getAreaHigherThan(cutHeights[i], cutDays[i]); if(cutAreas[i] != 0){ ahdt.setAreaHeight(0, cutAreas[i] - 1, cutHeights[i], cutDays[i]); } } cutAreas[MAX_M_N] = n; // fake cut at height 0, day 0, it cut whole area: n cutDays[MAX_M_N] = 0; cutHeights[MAX_M_N] = 0; totalWeights[MAX_M_N + 1] = 0; stack<long long int> descendingAreaCuts; // cut IDs on stack descendingAreaCuts.push(MAX_M_N); // adding fake cut on the bottom, no harm totalWeights[0] = 0; for(long long int i=0; i<m; ++i){ while(cutAreas[descendingAreaCuts.top()] < cutAreas[i]) descendingAreaCuts.pop(); long long int previousCutID = descendingAreaCuts.top(); totalWeights[i + 1] = (cutDays[i] - cutDays[previousCutID])*areaGrowth[cutAreas[i]] - cutAreas[i]*(cutHeights[i]-cutHeights[previousCutID]) + totalWeights[previousCutID + 1]; descendingAreaCuts.push(i); } // Based on total weights, calculate individual weights for(long long int i=0; i<m; ++i){ cout << (totalWeights[i + 1] - totalWeights[i]) << '\n'; } cout.flush(); return 0; }
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 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 | // Potyczki Algorytmiczne 2015 // runda 1 // SIAno // Tomasz Pastusiak #include <iostream> #include <algorithm> #include <functional> #include <stack> using namespace std; #define MAX_M_N 500000 //#define MAX_M_N 5 //#define MAX_M_N 4 long long int growthSpeed[MAX_M_N]; long long int cutDays[MAX_M_N + 1]; // place for fake 0 height cut at day 0 long long int cutHeights[MAX_M_N + 1]; // place for fake 0 height cut at day 0 long long int cutAreas[MAX_M_N + 1]; // place for fake 0 height cut at day 0 long long int areaGrowth[MAX_M_N + 1]; // total growth on area 0..(i-1) long long int totalWeights[MAX_M_N + 2]; // total weight cut grass after i'th cut (0 cuts give 0 grass), additional +1 for fake cut // entries in the tree numbered from 1 to 2*n - 1 // base elements have numbers: n + 0 ..... n + n - 1 // information is stored on areas ( log(n) ) // information is retrieved from points by traversing to the root ( log(n) ) class AreaHeightDateTree{ public: long long int heightTree[MAX_M_N*2]; long long int dateTree[MAX_M_N*2]; long long int n; long long int size; void setSize(long long int n){ this->n = n; size = 2*n; for(long long int i=1;i<size;++i){ heightTree[i] = 0; // grass height at time 0 = 0 dateTree[i] = 0; } } long long int getHeight(long long int position, long long int currentDate){ long long int node = n + position; long long int storedHeight = heightTree[node]; long long int storedDate = dateTree[node]; while (node != 1) { node /= 2; if(dateTree[node] > storedDate){ storedHeight = heightTree[node]; storedDate = dateTree[node]; } } long long int currentHeight = storedHeight + (currentDate - storedDate)*(long long int)growthSpeed[position]; return currentHeight; } // get current height at position void setAreaHeight(long long int areaFrom, long long int areaTo, long long int height, long long int currentDate){ long long int nl = n + areaFrom, nr = n + areaTo; // node left, node right heightTree[nl] = heightTree[nr] = height; dateTree[nl] = dateTree[nr] = currentDate; while (nl / 2 != nr / 2) { if (nl % 2 == 0){ heightTree[nl + 1] = height; dateTree[nl + 1] = currentDate; } // if left node is left child of some parent, save info in right brother if (nr % 2 == 1){ heightTree[nr - 1] = height; dateTree[nr - 1] = currentDate; } // if right node is right child of some parent, save info in left brother nl /= 2; nr /= 2; } } long long int getAreaHigherThan(long long int height, long long int currentDate){ // use binary search long long int l = 0, r = n, mid; while(l != r){ mid = (l + r)/2; long long int midHeight = getHeight(mid, currentDate); if(midHeight > height) l = mid + 1; else r = mid; } return l; // or r } // get Area higher than }; AreaHeightDateTree ahdt; int main(){ ios_base::sync_with_stdio(false); long long int n, m; cin >> n >> m; for(long long int i=0; i<n ;++i){ cin >> growthSpeed[i]; } for(long long int i=0; i<m; ++i){ cin >> cutDays[i] >> cutHeights[i]; } // DATA LOADED // for algorithm to work, growthSpeed has to be sorted sort(growthSpeed, growthSpeed + n, greater<long long int>()); areaGrowth[0] = 0; // area of size 0 do not grow at all for(long long int i=0; i<n ;++i){ areaGrowth[i + 1] = areaGrowth[i] + growthSpeed[i]; } ahdt.setSize(n); // lets calculate cut areas using AreaHeightDateTree for(long long int i=0; i<m; ++i){ cutAreas[i] = ahdt.getAreaHigherThan(cutHeights[i], cutDays[i]); if(cutAreas[i] != 0){ ahdt.setAreaHeight(0, cutAreas[i] - 1, cutHeights[i], cutDays[i]); } } cutAreas[MAX_M_N] = n; // fake cut at height 0, day 0, it cut whole area: n cutDays[MAX_M_N] = 0; cutHeights[MAX_M_N] = 0; totalWeights[MAX_M_N + 1] = 0; stack<long long int> descendingAreaCuts; // cut IDs on stack descendingAreaCuts.push(MAX_M_N); // adding fake cut on the bottom, no harm totalWeights[0] = 0; for(long long int i=0; i<m; ++i){ while(cutAreas[descendingAreaCuts.top()] < cutAreas[i]) descendingAreaCuts.pop(); long long int previousCutID = descendingAreaCuts.top(); totalWeights[i + 1] = (cutDays[i] - cutDays[previousCutID])*areaGrowth[cutAreas[i]] - cutAreas[i]*(cutHeights[i]-cutHeights[previousCutID]) + totalWeights[previousCutID + 1]; descendingAreaCuts.push(i); } // Based on total weights, calculate individual weights for(long long int i=0; i<m; ++i){ cout << (totalWeights[i + 1] - totalWeights[i]) << '\n'; } cout.flush(); return 0; } |