#include <algorithm> #include <cstdio> long long int current_time; struct TreeNode { int slowest_grass_; int fastest_grass_; long long int lowest_grass_; long long int highest_grass_; long long int mass_of_grass_; long long int sum_of_velocities_; long long int last_update_; long long int setting_time_; long long int setting_height_; void InitJoin(const TreeNode& l, const TreeNode& r) { slowest_grass_ = std::min(l.slowest_grass_, r.slowest_grass_); fastest_grass_ = std::max(l.fastest_grass_, r.fastest_grass_); sum_of_velocities_ = l.sum_of_velocities_ + r.sum_of_velocities_; } void Join(const TreeNode& l, const TreeNode& r) { lowest_grass_ = std::min(l.lowest_grass_, r.lowest_grass_); highest_grass_ = std::max(l.highest_grass_, r.highest_grass_); mass_of_grass_ = l.mass_of_grass_ + r.mass_of_grass_; sum_of_velocities_ = l.sum_of_velocities_ + r.sum_of_velocities_; } void SetTo(long long int height, TreeNode* l, TreeNode* r, int length) { setting_time_ = current_time; setting_height_ = height; Update(l, r, length); } void Update(TreeNode* l, TreeNode* r, int length) { if (setting_time_ >= 0) { lowest_grass_ = setting_height_; highest_grass_ = setting_height_; mass_of_grass_ = length * setting_height_; last_update_ = setting_time_; if (l != nullptr and r != nullptr) { // Not a leaf. r->setting_time_ = l->setting_time_ = setting_time_; r->setting_height_ = l->setting_height_ = setting_height_; } setting_time_ = -1ll; } const long long int time_difference = current_time - last_update_; lowest_grass_ += time_difference * slowest_grass_; highest_grass_ += time_difference * fastest_grass_; mass_of_grass_ += time_difference * sum_of_velocities_; last_update_ = current_time; } }; int n2; const int moreThanBase = 524288 + 5; TreeNode tree[moreThanBase * 2 + 5]; TreeNode* LeftSon(int w) { return w < n2 ? &tree[w * 2] : nullptr; } TreeNode* RightSon(int w) { return w < n2 ? &tree[w * 2 + 1] : nullptr; } long long int Cut(int w, int a, int b, long long height) { long long result = 0ll; TreeNode& t = tree[w]; t.Update(LeftSon(w), RightSon(w), b - a + 1); if (t.lowest_grass_ >= height) { result = t.mass_of_grass_ - (b - a + 1) * height; t.SetTo(height, LeftSon(w), RightSon(w), b - a + 1); } else if (t.highest_grass_ <= height) { // Do nothing. } else if (a != b) { result = Cut(w * 2, a, (a + b) / 2, height) + Cut(w * 2 + 1, (a + b + 1) / 2, b, height); t.Join(tree[w * 2], tree[w * 2 + 1]); } return result; } int n, m; int a_i[moreThanBase + 5]; int main() { scanf("%d%d", &n, &m); n2 = 1; while (n2 < n) { n2 *= 2; } for (int i = 0; i < n; i++) { scanf("%d", &a_i[i]); } std::sort(a_i, a_i + n2); // Additional zeroes are sorted on purpose. for (int i = 0; i < n2; i++) { tree[n2 + i].slowest_grass_ = a_i[i]; tree[n2 + i].fastest_grass_ = a_i[i]; tree[n2 + i].sum_of_velocities_ = a_i[i]; } for (int i = n2 - 1; i >= 1; i--) { tree[i].InitJoin(tree[i * 2], tree[i * 2 + 1]); } while (m--) { long long int height; scanf("%lld%lld", ¤t_time, &height); // current_time = d, height = b printf("%lld\n", Cut(1, 0, n2 - 1, height)); } 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 | #include <algorithm> #include <cstdio> long long int current_time; struct TreeNode { int slowest_grass_; int fastest_grass_; long long int lowest_grass_; long long int highest_grass_; long long int mass_of_grass_; long long int sum_of_velocities_; long long int last_update_; long long int setting_time_; long long int setting_height_; void InitJoin(const TreeNode& l, const TreeNode& r) { slowest_grass_ = std::min(l.slowest_grass_, r.slowest_grass_); fastest_grass_ = std::max(l.fastest_grass_, r.fastest_grass_); sum_of_velocities_ = l.sum_of_velocities_ + r.sum_of_velocities_; } void Join(const TreeNode& l, const TreeNode& r) { lowest_grass_ = std::min(l.lowest_grass_, r.lowest_grass_); highest_grass_ = std::max(l.highest_grass_, r.highest_grass_); mass_of_grass_ = l.mass_of_grass_ + r.mass_of_grass_; sum_of_velocities_ = l.sum_of_velocities_ + r.sum_of_velocities_; } void SetTo(long long int height, TreeNode* l, TreeNode* r, int length) { setting_time_ = current_time; setting_height_ = height; Update(l, r, length); } void Update(TreeNode* l, TreeNode* r, int length) { if (setting_time_ >= 0) { lowest_grass_ = setting_height_; highest_grass_ = setting_height_; mass_of_grass_ = length * setting_height_; last_update_ = setting_time_; if (l != nullptr and r != nullptr) { // Not a leaf. r->setting_time_ = l->setting_time_ = setting_time_; r->setting_height_ = l->setting_height_ = setting_height_; } setting_time_ = -1ll; } const long long int time_difference = current_time - last_update_; lowest_grass_ += time_difference * slowest_grass_; highest_grass_ += time_difference * fastest_grass_; mass_of_grass_ += time_difference * sum_of_velocities_; last_update_ = current_time; } }; int n2; const int moreThanBase = 524288 + 5; TreeNode tree[moreThanBase * 2 + 5]; TreeNode* LeftSon(int w) { return w < n2 ? &tree[w * 2] : nullptr; } TreeNode* RightSon(int w) { return w < n2 ? &tree[w * 2 + 1] : nullptr; } long long int Cut(int w, int a, int b, long long height) { long long result = 0ll; TreeNode& t = tree[w]; t.Update(LeftSon(w), RightSon(w), b - a + 1); if (t.lowest_grass_ >= height) { result = t.mass_of_grass_ - (b - a + 1) * height; t.SetTo(height, LeftSon(w), RightSon(w), b - a + 1); } else if (t.highest_grass_ <= height) { // Do nothing. } else if (a != b) { result = Cut(w * 2, a, (a + b) / 2, height) + Cut(w * 2 + 1, (a + b + 1) / 2, b, height); t.Join(tree[w * 2], tree[w * 2 + 1]); } return result; } int n, m; int a_i[moreThanBase + 5]; int main() { scanf("%d%d", &n, &m); n2 = 1; while (n2 < n) { n2 *= 2; } for (int i = 0; i < n; i++) { scanf("%d", &a_i[i]); } std::sort(a_i, a_i + n2); // Additional zeroes are sorted on purpose. for (int i = 0; i < n2; i++) { tree[n2 + i].slowest_grass_ = a_i[i]; tree[n2 + i].fastest_grass_ = a_i[i]; tree[n2 + i].sum_of_velocities_ = a_i[i]; } for (int i = n2 - 1; i >= 1; i--) { tree[i].InitJoin(tree[i * 2], tree[i * 2 + 1]); } while (m--) { long long int height; scanf("%lld%lld", ¤t_time, &height); // current_time = d, height = b printf("%lld\n", Cut(1, 0, n2 - 1, height)); } return 0; } |