23:I[344796,["/_next/static/chunks/083cs_iw_ie0y.js","/_next/static/chunks/2sk2f47durg8o.js","/_next/static/chunks/00mfjk9z2ewie.js","/_next/static/chunks/2q9x6spyz4qxv.js","/_next/static/chunks/1wo5i8je1ygp5.js","/_next/static/chunks/05nh6118fe45j.js","/_next/static/chunks/2qcnia-og0qh0.js","/_next/static/chunks/3b7nv_cf1l4bq.js"],"default"] 29:I[27201,["/_next/static/chunks/083cs_iw_ie0y.js","/_next/static/chunks/2sk2f47durg8o.js","/_next/static/chunks/00mfjk9z2ewie.js","/_next/static/chunks/2q9x6spyz4qxv.js","/_next/static/chunks/1wo5i8je1ygp5.js","/_next/static/chunks/05nh6118fe45j.js","/_next/static/chunks/2qcnia-og0qh0.js"],"IconMark"] 24:Tf95,

An analyst on a financial team is studying an unbounded row of bags. The bags are numbered 1, 2, 3, … and, in principle, the row continues forever. Every bag holds some amount of money, and the analyst wants to pick a block of exactly k consecutive bags whose total money is as large as possible.

The amounts of money are described by a collection of n segments. Each segment is a triple [L, R, V], meaning that every bag whose number lies in the inclusive range L … R contains exactly V units of money. The segments are pairwise non-overlapping, so no bag is described by more than one segment. Any bag that is not covered by any segment contains 0 money.

Among all possible blocks of k consecutive bags (a block may start at any bag number ≥ 1 and may extend over bags that hold no money), find the maximum possible total amount of money contained in one block. Because this total can be very large, print it modulo 1000000007 (that is, 10^9 + 7).

Input Format

The first line contains a single integer k, the number of consecutive bags in a block.
The second line contains a single integer n, the number of segments.
The third line contains the integer 3, the number of columns of the segment array (each segment has exactly three values).
Each of the next n lines contains three space-separated integers L, R, and V, describing one segment: bags L through R (inclusive) each hold V units of money.

Output Format

Print a single integer: the maximum total money over any block of k consecutive bags, taken modulo 1000000007.

Constraints

1 ≤ k ≤ 10^9
1 ≤ n ≤ 10^5
1 ≤ L ≤ R ≤ 10^9
1 ≤ V ≤ 10^9
The n segments are pairwise non-overlapping.

Note that the true (pre-modulo) total can exceed the range of a 32-bit integer, so a 64-bit accumulator is required, and the modulo must be applied only to the final maximum — never while comparing candidate blocks.

Example

Input

Output

Explanation

The segments assign money to the bags as follows:

Bag   : 1  2  3  4  5  6  7  8  9  10
Money : 2  2  2  2  0  5  7  0  1  1

All other bags hold 0. With k = 5, some candidate blocks are:

Bags 1 … 5: 2 + 2 + 2 + 2 + 0 = 8
Bags 2 … 6: 2 + 2 + 2 + 0 + 5 = 11
Bags 3 … 7: 2 + 2 + 0 + 5 + 7 = 16
Bags 6 … 10: 5 + 7 + 0 + 1 + 1 = 14

The best block is bags 3 … 7 with a total of 16, so the answer is 16 mod (10^9 + 7) = 16.

Notes

A block always consists of exactly k bags; it may include bags with 0 money (including gaps between segments and bags past the last segment).
Ranges are inclusive on both ends: a segment [L, R, V] covers R - L + 1 bags, each worth V.
The maximum is taken over the true totals; apply the modulo only to the final answer.
If k is large enough to span every segment at once, the answer is the total money across all segments (modulo 10^9 + 7).

25:T72c,#include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long k; int n, cols; if (!(cin >> k >> n >> cols)) return 0; vector> segs(n); for (int i = 0; i < n; i++) { cin >> segs[i][0] >> segs[i][1] >> segs[i][2]; // L R V } sort(segs.begin(), segs.end()); vector Ls(n), Rs(n), Vs(n); vector pref(n + 1, 0); for (int i = 0; i < n; i++) { Ls[i] = segs[i][0]; Rs[i] = segs[i][1]; Vs[i] = segs[i][2]; pref[i + 1] = pref[i] + Vs[i] * (Rs[i] - Ls[i] + 1); } auto window_sum = [&](long long x) -> long long { long long y = x + k - 1; // first segment with R >= x (Rs sorted ascending) int lo = (int)(lower_bound(Rs.begin(), Rs.end(), x) - Rs.begin()); if (lo >= n || Ls[lo] > y) return 0; // last segment with L <= y int hi = (int)(upper_bound(Ls.begin(), Ls.end(), y) - Ls.begin()) - 1; if (hi < lo) return 0; if (lo == hi) { return Vs[lo] * (min(Rs[lo], y) - max(Ls[lo], x) + 1); } long long total = pref[hi] - pref[lo + 1]; total += Vs[lo] * (Rs[lo] - max(Ls[lo], x) + 1); total += Vs[hi] * (min(Rs[hi], y) - Ls[hi] + 1); return total; }; // candidate window starts vector cands; cands.push_back(1); for (int i = 0; i < n; i++) { long long arr[4] = {Ls[i], Ls[i] - k, Rs[i] + 1, Rs[i] - k + 1}; for (long long c : arr) if (c >= 1) cands.push_back(c); } long long best = 0; for (long long x : cands) { long long v = window_sum(x); if (v > best) best = v; } const long long MOD = 1000000007LL; cout << (best % MOD) << "\n"; return 0; } 26:T770,import sys from bisect import bisect_left, bisect_right MOD = 1000000007 def solve(k, segs): # segs: list of (L, R, V), pairwise non-overlapping, 1<=L<=R segs = sorted(segs) n = len(segs) Ls = [s[0] for s in segs] Rs = [s[1] for s in segs] Vs = [s[2] for s in segs] # prefix of full-segment money: pref[i] = sum_{j= x (Rs is sorted since disjoint+sorted by L) lo = bisect_left(Rs, x) if lo >= n or Ls[lo] > y: return 0 # last segment with L <= y hi = bisect_right(Ls, y) - 1 if hi < lo: return 0 if lo == hi: L, R, V = Ls[lo], Rs[lo], Vs[lo] return V * (min(R, y) - max(L, x) + 1) # middle segments lo+1..hi-1 fully contained total = pref[hi] - pref[lo + 1] # clip left (lo) and right (hi) total += Vs[lo] * (Rs[lo] - max(Ls[lo], x) + 1) total += Vs[hi] * (min(Rs[hi], y) - Ls[hi] + 1) return total cands = {1} for i in range(n): for c in (Ls[i], Ls[i] - k, Rs[i] + 1, Rs[i] - k + 1): if c >= 1: cands.add(c) best = 0 for x in cands: v = window_sum(x) if v > best: best = v return best % MOD def main(): data = sys.stdin.read().split() idx = 0 k = int(data[idx]); idx += 1 n = int(data[idx]); idx += 1 cols = int(data[idx]); idx += 1 # column size, always 3 segs = [] for _ in range(n): L = int(data[idx]); R = int(data[idx + 1]); V = int(data[idx + 2]) idx += 3 segs.append((L, R, V)) print(solve(k, segs)) if __name__ == "__main__": main() 27:Tc27,# Maximum Money in K Consecutive Bags ## Problem Description An analyst on a financial team is studying an unbounded row of bags. The bags are numbered `1, 2, 3, …` and, in principle, the row continues forever. Every bag holds some amount of money, and the analyst wants to pick a block of **exactly `k` consecutive bags** whose total money is as large as possible. The amounts of money are described by a collection of `n` **segments**. Each segment is a triple `[L, R, V]`, meaning that every bag whose number lies in the inclusive range `L … R` contains exactly `V` units of money. The segments are pairwise **non-overlapping**, so no bag is described by more than one segment. Any bag that is not covered by any segment contains `0` money. Among all possible blocks of `k` consecutive bags (a block may start at any bag number `≥ 1` and may extend over bags that hold no money), find the maximum possible total amount of money contained in one block. Because this total can be very large, print it modulo `1000000007` (that is, `10^9 + 7`). ## Input Format - The first line contains a single integer `k`, the number of consecutive bags in a block. - The second line contains a single integer `n`, the number of segments. - The third line contains the integer `3`, the number of columns of the segment array (each segment has exactly three values). - Each of the next `n` lines contains three space-separated integers `L`, `R`, and `V`, describing one segment: bags `L` through `R` (inclusive) each hold `V` units of money. ## Output Format Print a single integer: the maximum total money over any block of `k` consecutive bags, taken modulo `1000000007`. ## Constraints - `1 ≤ k ≤ 10^9` - `1 ≤ n ≤ 10^5` - `1 ≤ L ≤ R ≤ 10^9` - `1 ≤ V ≤ 10^9` - The `n` segments are pairwise non-overlapping. Note that the true (pre-modulo) total can exceed the range of a 32-bit integer, so a 64-bit accumulator is required, and the modulo must be applied only to the final maximum — never while comparing candidate blocks. ## Example **Input** ``` 5 4 3 1 4 2 6 6 5 7 7 7 9 10 1 ``` **Output** ``` 16 ``` **Explanation** The segments assign money to the bags as follows: ``` Bag : 1 2 3 4 5 6 7 8 9 10 Money : 2 2 2 2 0 5 7 0 1 1 ``` All other bags hold `0`. With `k = 5`, some candidate blocks are: - Bags `1 … 5`: `2 + 2 + 2 + 2 + 0 = 8` - Bags `2 … 6`: `2 + 2 + 2 + 0 + 5 = 11` - Bags `3 … 7`: `2 + 2 + 0 + 5 + 7 = 16` - Bags `6 … 10`: `5 + 7 + 0 + 1 + 1 = 14` The best block is bags `3 … 7` with a total of `16`, so the answer is `16 mod (10^9 + 7) = 16`. ## Notes - A block always consists of **exactly `k`** bags; it may include bags with `0` money (including gaps between segments and bags past the last segment). - Ranges are **inclusive** on both ends: a segment `[L, R, V]` covers `R - L + 1` bags, each worth `V`. - The maximum is taken over the **true** totals; apply the modulo only to the final answer. - If `k` is large enough to span every segment at once, the answer is the total money across all segments (modulo `10^9 + 7`).28:Tb8e,# Maximum Money in K Consecutive Bags ## Overview We are given a set of non-overlapping segments over an effectively infinite line of bags, where segment `[L, R, V]` puts value `V` on every bag in `L … R`. We must slide a window of exactly `k` consecutive bags and report the maximum total value it can cover, modulo `10^9 + 7`. ## Key Insight The money function over bag positions is a step function: it is constant on each segment, `0` on the gaps, and there are only `2n` distinct boundaries. The total inside a width-`k` window is a piecewise-linear function of the window's left endpoint `x`. A piecewise-linear function on an integer domain attains its maximum at a breakpoint, and breakpoints occur only where the window's left edge or right edge crosses a segment boundary. Therefore only `O(n)` candidate window positions need to be examined: for each segment, `x = L`, `x = L - k`, `x = R + 1`, and `x = R - k + 1` (clamped to `x ≥ 1`). ## Approach Sort the segments by `L`; because they are disjoint, `R` is then sorted too. Build a prefix-sum array over each segment's full contribution `V · (R - L + 1)`. For a candidate window `[x, x + k - 1]`, the intersecting segments form a contiguous range in sorted order: locate the first segment with `R ≥ x` and the last with `L ≤ y` using binary search. Every intersecting segment strictly between those two endpoints lies fully inside the window (disjointness guarantees it), so its contribution comes straight from the prefix sums; only the first and last intersecting segments may be clipped, and each is clipped with `min(R, y) - max(L, x) + 1`. Evaluate all `O(n)` candidates and keep the largest total. Apply the modulo once, to that maximum. ## Why This Works Enumerating breakpoints is exhaustive for the maximum of a piecewise-linear function, so the best window is guaranteed to be one of the candidates. The contiguity of intersecting segments follows from disjointness: any segment sandwiched between two other intersecting segments cannot be clipped, so counting middle segments in full is exact, and clipping is needed only at the two ends. ## Complexity Sorting is `O(n log n)`; each of the `O(n)` candidates is evaluated in `O(log n)` with binary search over the prefix sums, giving `O(n log n)` overall time and `O(n)` extra space. ## Common Pitfalls - Comparing window totals after taking them modulo `10^9 + 7`; the maximum must be chosen on true values and reduced only at the end. - Using a 32-bit accumulator: coordinates and values reach `10^9`, so a window total can exceed `2^31` and needs 64-bit arithmetic. - Considering only left-aligned windows and missing optima where the window's right edge aligns with a segment end (the sample is exactly such a case). - Forgetting the `+ 1` in the inclusive overlap length `min(R, y) - max(L, x) + 1`. - Failing to clip a boundary segment (counting it in full) when the window starts or ends in the middle of it.1c:[["$","script",null,{"type":"application/ld+json","dangerouslySetInnerHTML":{"__html":"{\"@context\":\"https://schema.org\",\"@type\":\"LearningResource\",\"learningResourceType\":\"Coding Question\",\"name\":\"Maximum Money in K Consecutive Bags\",\"description\":\"An analyst on a financial team is studying an unbounded row of bags. The bags are numbered 1, 2, 3, … and, in principle, the row continues forever. Every bag holds some amount of money, and the analyst wants to pick a block of exactly k consecutive bags whose total money is as large as possible. The amounts of money are described by a collection of n segments . Each segment is a triple [L, R, V] , meaning that every bag whose number lies in the inclusive range L … R contains exactly V units of m\",\"educationalLevel\":\"medium\",\"about\":{\"@type\":\"Organization\",\"name\":\"User Submitted_24july\"},\"provider\":{\"@type\":\"Organization\",\"name\":\"OAHelper\",\"url\":\"https://oahelper.in\"},\"isPartOf\":{\"@type\":\"WebSite\",\"name\":\"OAHelper\",\"url\":\"https://oahelper.in\"},\"url\":\"https://oahelper.in/problems/NTM0N3ww/maximum-money-in-k-consecutive-bags\"}"}}],["$","script",null,{"type":"application/ld+json","dangerouslySetInnerHTML":{"__html":"{\"@context\":\"https://schema.org\",\"@type\":\"BreadcrumbList\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https://oahelper.in/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Problems\",\"item\":\"https://oahelper.in/problems\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Maximum Money in K Consecutive Bags\",\"item\":\"https://oahelper.in/problems/NTM0N3ww/maximum-money-in-k-consecutive-bags\"}]}"}}],["$","section",null,{"className":"sr-only","aria-hidden":"true","children":[["$","p",null,{"children":["Company: ","User Submitted_24july"]}],["$","p",null,{"children":["Difficulty: ","medium"]}],false,["$","div",null,{"children":[["$","h2",null,{"children":"Problem Statement"}],["$","p",null,{"children":"An analyst on a financial team is studying an unbounded row of bags. The bags are numbered 1, 2, 3, … and, in principle, the row continues forever. Every bag holds some amount of money, and the analyst wants to pick a block of exactly k consecutive bags whose total money is as large as possible. The amounts of money are described by a collection of n segments . Each segment is a triple [L, R, V] , meaning that every bag whose number lies in the inclusive range L … R contains exactly V units of money. The segments are pairwise non-overlapping , so no bag is described by more than one segment. Any bag that is not covered by any segment contains 0 money. Among all possible blocks of k consecutive bags (a block may start at any bag number ≥ 1 and may extend over bags that hold no money), find the maximum possible total amount of money contained in one block. Because this total can be very large, print it modulo 1000000007 (that is, 10^9 + 7 ). Input Format The first line contains a single "}]]}],false,["$","nav",null,{"aria-label":"Related company pages","children":[["$","$Lb",null,{"href":"/company-questions/user-submitted24july","children":["More ","User Submitted_24july"," OA questions"]}],["$","$Lb",null,{"href":"/interview-experiences","children":"Interview experiences"}]]}]]}],["$","$L23",null,{"id":"NTM0N3ww","initialQuestion":{"id":"NTM0N3ww","title":"Maximum Money in K Consecutive Bags","google_doc_link":null,"problem_statement":"$24","solution_cpp":"$25","solution_python":"$26","solution_java":null,"pregiven_code_cpp":"#include \nusing namespace std;\n\nint calculateMaximumConsecutiveSum(int k, vector> segment) {\n // Write your code here\n return 0;\n}\n\nint main() {\n ios::sync_with_stdio(false);\n cin.tie(nullptr);\n\n int k, n, cols;\n if (!(cin >> k >> n >> cols)) return 0;\n\n vector> segment(n, vector(3));\n for (int i = 0; i < n; i++) {\n cin >> segment[i][0] >> segment[i][1] >> segment[i][2];\n }\n\n cout << calculateMaximumConsecutiveSum(k, segment) << \"\\n\";\n return 0;\n}\n","pregiven_code_python":"import sys\n\n\ndef calculateMaximumConsecutiveSum(k, segment):\n # segment is a list of [L, R, V] triples.\n # Write your code here\n return 0\n\n\ndef main():\n data = sys.stdin.read().split()\n idx = 0\n k = int(data[idx]); idx += 1\n n = int(data[idx]); idx += 1\n cols = int(data[idx]); idx += 1 # always 3\n segment = []\n for _ in range(n):\n L = int(data[idx]); R = int(data[idx + 1]); V = int(data[idx + 2])\n idx += 3\n segment.append([L, R, V])\n print(calculateMaximumConsecutiveSum(k, segment))\n\n\nif __name__ == \"__main__\":\n main()\n","pregiven_code_java":"import java.util.*;\nimport java.io.*;\n\npublic class Solution {\n\n static int calculateMaximumConsecutiveSum(int k, int[][] segment) {\n // Write your code here\n return 0;\n }\n\n public static void main(String[] args) throws IOException {\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n StreamTokenizer st = new StreamTokenizer(br);\n st.nextToken(); int k = (int) st.nval;\n st.nextToken(); int n = (int) st.nval;\n st.nextToken(); // cols, always 3\n int[][] segment = new int[n][3];\n for (int i = 0; i < n; i++) {\n st.nextToken(); segment[i][0] = (int) st.nval;\n st.nextToken(); segment[i][1] = (int) st.nval;\n st.nextToken(); segment[i][2] = (int) st.nval;\n }\n System.out.println(calculateMaximumConsecutiveSum(k, segment));\n }\n}\n","difficulty":"medium","question_type":"coding","premium_required":0,"created_at":"2026-07-26T19:09:05.624287+00:00","updated_at":"2026-08-10T00:01:51.812599+00:00","solution_code":null,"solution":null,"pregiven_code":"#include \nusing namespace std;\n\nint calculateMaximumConsecutiveSum(int k, vector> segment) {\n // Write your code here\n return 0;\n}\n\nint main() {\n ios::sync_with_stdio(false);\n cin.tie(nullptr);\n\n int k, n, cols;\n if (!(cin >> k >> n >> cols)) return 0;\n\n vector> segment(n, vector(3));\n for (int i = 0; i < n; i++) {\n cin >> segment[i][0] >> segment[i][1] >> segment[i][2];\n }\n\n cout << calculateMaximumConsecutiveSum(k, segment) << \"\\n\";\n return 0;\n}\n","input_test_case":"[\"5\\n4\\n3\\n1 4 2\\n6 6 5\\n7 7 7\\n9 10 1\\n\", \"1\\n1\\n3\\n1 1 1\\n\"]","output_test_case":"[\"16\", \"1\"]","lc_tags":"[\"Array\", \"Sorting\", \"Prefix Sum\", \"Binary Search\", \"Sliding Window\", \"Greedy\"]","visual_animation":null,"difficulty_score":45,"md_problem_statement":"$27","unique_company_name":"user submitted","sql_solution":null,"bash_solution":null,"js_solution":null,"editorial":"$28","hidden_test_cases_blob_count":80,"youtube_tutorial":null,"prompt_solution":null,"campus_type":"on_campus","college_name":null,"role":null,"hidden_test_cases_ref":null,"is_mock_oa":false,"publication_status":"published","has_image":true,"company_name":"User Submitted_24july","is_first_in_company":true,"company_ref":"MTYzNnww","total_test_cases":5,"hidden_test_cases_count":3},"isQotdToday":false,"qotdReward":5}]] 1e:null 22:[["$","title","0",{"children":"Maximum Money in K Consecutive Bags - User Submitted_24july OA Question | OAHelper"}],["$","meta","1",{"name":"description","content":"Maximum Money in K Consecutive Bags (User Submitted_24july OA) - medium: An analyst on a financial team is studying an unbounded row of bags. The bags are numbered 1, 2, 3, … and, in principle, the row continues forever. Every bag ho…"}],["$","meta","2",{"name":"author","content":"OAHelper Team"}],["$","meta","3",{"name":"keywords","content":"User Submitted_24july OA question, User Submitted_24july online assessment, Maximum Money in K Consecutive Bags, medium, online assessment, coding question, OA practice, interview preparation"}],["$","meta","4",{"name":"robots","content":"index, follow"}],["$","meta","5",{"name":"googlebot","content":"index, follow, max-video-preview:-1, max-image-preview:large, max-snippet:-1"}],["$","link","6",{"rel":"canonical","href":"https://oahelper.in/problems/NTM0N3ww/maximum-money-in-k-consecutive-bags"}],["$","meta","7",{"name":"google-site-verification","content":"MCxApq58khiH0y4KRigRUpoTS3ckefkhoCSHRIRLiXo"}],["$","meta","8",{"property":"og:title","content":"Maximum Money in K Consecutive Bags - User Submitted_24july OA Question | OAHelper"}],["$","meta","9",{"property":"og:description","content":"Maximum Money in K Consecutive Bags (User Submitted_24july OA) - medium: An analyst on a financial team is studying an unbounded row of bags. The bags are numbered 1, 2, 3, … and, in principle, the row continues forever. Every bag ho…"}],["$","meta","10",{"property":"og:url","content":"https://oahelper.in/problems/NTM0N3ww/maximum-money-in-k-consecutive-bags"}],["$","meta","11",{"property":"og:site_name","content":"OAHelper"}],["$","meta","12",{"property":"og:image","content":"https://oahelper.in/campus-ceo-favicon.png?v=11"}],["$","meta","13",{"property":"og:image:width","content":"256"}],["$","meta","14",{"property":"og:image:height","content":"256"}],["$","meta","15",{"property":"og:image:alt","content":"Maximum Money in K Consecutive Bags - User Submitted_24july OA Question"}],["$","meta","16",{"property":"og:type","content":"website"}],["$","meta","17",{"name":"twitter:card","content":"summary_large_image"}],["$","meta","18",{"name":"twitter:title","content":"Maximum Money in K Consecutive Bags - User Submitted_24july OA Question | OAHelper"}],["$","meta","19",{"name":"twitter:description","content":"Maximum Money in K Consecutive Bags (User Submitted_24july OA) - medium: An analyst on a financial team is studying an unbounded row of bags. The bags are numbered 1, 2, 3, … and, in principle, the row continues forever. Every bag ho…"}],["$","meta","20",{"name":"twitter:image","content":"https://oahelper.in/campus-ceo-favicon.png?v=11"}],["$","link","21",{"rel":"shortcut icon","href":"/campus-ceo-favicon.png?v=11"}],["$","link","22",{"rel":"icon","href":"/campus-ceo-favicon-128.png?v=11","sizes":"128x128","type":"image/png"}],["$","link","23",{"rel":"icon","href":"/campus-ceo-favicon.png?v=11","sizes":"256x256","type":"image/png"}],["$","link","24",{"rel":"icon","href":"/campus-ceo-favicon-512.png?v=11","sizes":"512x512","type":"image/png"}],["$","link","25",{"rel":"apple-touch-icon","href":"/campus-ceo-favicon-512.png?v=11","sizes":"180x180","type":"image/png"}],["$","$L29","26",{}]]