{"problem":{"name":"D. Rectangles","description":{"content":"Given an R×C grid with each cell containing an integer, find the number of subrectangles in this grid that contain only one distinct integer; this means every cell in a subrectangle contains the same ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10110D"},"statements":[{"statement_type":"Markdown","content":"Given an R×C grid with each cell containing an integer, find the number of subrectangles in this grid that contain only one distinct integer; this means every cell in a subrectangle contains the same integer.\n\nA subrectangle is defined by two cells: the top left cell (r1, c1), and the bottom-right cell (r2, c2) (1 ≤ r1 ≤ r2 ≤ R) (1 ≤ c1 ≤ c2 ≤ C), assuming that rows are numbered from top to bottom and columns are numbered from left to right.\n\nThe first line of input contains a single integer T, the number of test cases.\n\nThe first line of each test case contains two integers R and C (1 ≤ R, C ≤ 1000), the number of rows and the number of columns of the grid, respectively.\n\nEach of the next R lines contains C integers between 1 and 109, representing the values in the row.\n\nFor each test case, print the answer on a single line.\n\n## Input\n\nThe first line of input contains a single integer T, the number of test cases.The first line of each test case contains two integers R and C (1 ≤ R, C ≤ 1000), the number of rows and the number of columns of the grid, respectively.Each of the next R lines contains C integers between 1 and 109, representing the values in the row.\n\n## Output\n\nFor each test case, print the answer on a single line.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ R_k, C_k \\in \\mathbb{Z} $ denote the dimensions of the grid, with $ 1 \\leq R_k, C_k \\leq 1000 $.  \n- Let $ G_k = (g_{i,j})_{1 \\leq i \\leq R_k, 1 \\leq j \\leq C_k} $ be a matrix of integers where $ 1 \\leq g_{i,j} \\leq 10^9 $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq \\text{unspecified (implied by input)} $  \n2. For each test case $ k $:  \n   - $ 1 \\leq R_k, C_k \\leq 1000 $  \n   - $ g_{i,j} \\in \\mathbb{Z} $, $ 1 \\leq g_{i,j} \\leq 10^9 $ for all $ i,j $  \n\n**Objective**  \nFor each test case $ k $, compute the number of subrectangles defined by top-left $ (r_1, c_1) $ and bottom-right $ (r_2, c_2) $ with $ 1 \\leq r_1 \\leq r_2 \\leq R_k $, $ 1 \\leq c_1 \\leq c_2 \\leq C_k $, such that:  \n$$\n\\forall (i,j), (i',j') \\in [r_1, r_2] \\times [c_1, c_2], \\quad g_{i,j} = g_{i',j'}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10110D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}