35:I[290370,["/_next/static/immutable/chunks/0aneuidq2dd5s.js","/_next/static/immutable/chunks/3asdwddb65r_7.js","/_next/static/immutable/chunks/11qxjuvxxj8-v.js","/_next/static/immutable/chunks/2ol9wyej_s9h-.js","/_next/static/immutable/chunks/3dqr5h54-q26k.js","/_next/static/immutable/chunks/20gnsl3b8ay94.js","/_next/static/immutable/chunks/2v6773b5v9j_y.js","/_next/static/immutable/chunks/437mepgwkzb8b.js","/_next/static/immutable/chunks/03jf6lfc9r-so.js","/_next/static/immutable/chunks/1cty97j_3t4p8.js","/_next/static/immutable/chunks/1atq4abfx_cwi.js","/_next/static/immutable/chunks/29bm85rhaftys.js","/_next/static/immutable/chunks/3vuhqfn8nseb-.js","/_next/static/immutable/chunks/36tubk3midieh.js","/_next/static/immutable/chunks/2ke2tvdiokend.js","/_next/static/immutable/chunks/386n_qt61qywd.js","/_next/static/immutable/chunks/12nj9lbbxts99.js","/_next/static/immutable/chunks/2h62w_fdykycp.js","/_next/static/immutable/chunks/091zjp-oxk1vw.js","/_next/static/immutable/chunks/18bin06et1f2f.js","/_next/static/immutable/chunks/0q669txy1w1q5.js"],"default"] 36:I[218728,["/_next/static/immutable/chunks/0aneuidq2dd5s.js","/_next/static/immutable/chunks/3asdwddb65r_7.js","/_next/static/immutable/chunks/11qxjuvxxj8-v.js","/_next/static/immutable/chunks/2ol9wyej_s9h-.js","/_next/static/immutable/chunks/3dqr5h54-q26k.js","/_next/static/immutable/chunks/20gnsl3b8ay94.js","/_next/static/immutable/chunks/2v6773b5v9j_y.js","/_next/static/immutable/chunks/437mepgwkzb8b.js","/_next/static/immutable/chunks/03jf6lfc9r-so.js","/_next/static/immutable/chunks/1cty97j_3t4p8.js","/_next/static/immutable/chunks/1atq4abfx_cwi.js","/_next/static/immutable/chunks/29bm85rhaftys.js","/_next/static/immutable/chunks/3vuhqfn8nseb-.js","/_next/static/immutable/chunks/36tubk3midieh.js","/_next/static/immutable/chunks/2ke2tvdiokend.js","/_next/static/immutable/chunks/386n_qt61qywd.js","/_next/static/immutable/chunks/12nj9lbbxts99.js","/_next/static/immutable/chunks/2h62w_fdykycp.js","/_next/static/immutable/chunks/091zjp-oxk1vw.js","/_next/static/immutable/chunks/18bin06et1f2f.js","/_next/static/immutable/chunks/0q669txy1w1q5.js"],"default"] 37:T452,Consider one subarray and let $xt\}$ and $R=\min\{k>j:p_k>t\}$, using $L=0$ or $R=n+1$ when the corresponding position does not exist. The number of subarrays represented by this pair is $w(i,j)=(i-L)(R-j)$, because the left endpoint can be chosen from $L+1$ through $i$, and the right endpoint from $j$ through $R-1$. There are $T=(n-1)(n-2)/2$ subarrays of length at least $3$. Thus we may start with $T-\sum w(i,j)$ for the always-contributing subarrays, then add $w(i,j)$ for every pair with $d=1$ whose endpoints receive different colors.38:T12ea,#include #include "testlib.h" using namespace std; struct DSU { vector p, sz; explicit DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); } int find(int v) { if (p[v] == v) return v; return p[v] = find(p[v]); } bool unite(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (sz[a] < sz[b]) swap(a, b); p[b] = a; sz[a] += sz[b]; return true; } }; struct Fenwick { int n; vector bit; explicit Fenwick(int size) : n(size), bit(size + 1, 0) {} void add(int p) { for (; p <= n; p += p & -p) bit[p]++; } int sumPrefix(int p) const { int result = 0; for (; p > 0; p -= p & -p) result += bit[p]; return result; } int sumRange(int l, int r) const { if (l > r) return 0; return sumPrefix(r) - sumPrefix(l - 1); } }; int main(int argc, char* argv[]) { registerTestlibCmd(argc, argv); int t = inf.readInt(); for (int tc = 1; tc <= t; tc++) { int n = inf.readInt(); vector a(n + 1); long long total = 0; for (int i = 1; i <= n; i++) { a[i] = inf.readInt(); total += a[i]; } bool possible = total == 2LL * (n - 1); string verdict = ouf.readToken(); if (verdict != "Yes" && verdict != "No") { quitf(_wa, "test case %d: expected Yes or No", tc); } if (verdict == "No") { if (possible) { quitf(_wa, "test case %d: a valid tree exists", tc); } continue; } if (!possible) { quitf(_wa, "test case %d: no valid tree exists", tc); } vector> edges; vector> graph(n + 1); DSU dsu(n); for (int i = 0; i < n - 1; i++) { int u = ouf.readInt(1, n, "u"); int v = ouf.readInt(1, n, "v"); if (u == v) { quitf(_wa, "test case %d: a self-loop was printed", tc); } if (!dsu.unite(u, v)) { quitf(_wa, "test case %d: the printed edges contain a cycle", tc); } edges.push_back({min(u, v), max(u, v)}); graph[u].push_back(v); graph[v].push_back(u); } sort(edges.begin(), edges.end()); Fenwick fenwick(n); for (int left = 0; left < n - 1;) { int right = left; while (right < n - 1 && edges[right].first == edges[left].first) right++; for (int i = left; i < right; i++) { int l = edges[i].first; int r = edges[i].second; if (fenwick.sumRange(l + 1, r - 1) > 0) { quitf(_wa, "test case %d: two printed edges cross", tc); } } for (int i = left; i < right; i++) { fenwick.add(edges[i].second); } left = right; } int log = 1; while ((1 << log) <= n) log++; vector depth(n + 1, 0), order = {1}; vector> up(log, vector(n + 1, 1)); for (int it = 0; it < (int)order.size(); it++) { int v = order[it]; for (int to : graph[v]) { if (to == up[0][v]) continue; up[0][to] = v; depth[to] = depth[v] + 1; order.push_back(to); } } if ((int)order.size() != n) { quitf(_wa, "test case %d: the printed graph is disconnected", tc); } for (int j = 1; j < log; j++) { for (int v = 1; v <= n; v++) { up[j][v] = up[j - 1][up[j - 1][v]]; } } auto lca = [&](int x, int y) { if (depth[x] < depth[y]) swap(x, y); int difference = depth[x] - depth[y]; for (int j = 0; j < log; j++) { if ((difference >> j) & 1) x = up[j][x]; } if (x == y) return x; for (int j = log - 1; j >= 0; j--) { if (up[j][x] != up[j][y]) { x = up[j][x]; y = up[j][y]; } } return up[0][x]; }; for (int i = 1; i <= n; i++) { int j = i == n ? 1 : i + 1; int w = lca(i, j); int distance = depth[i] + depth[j] - 2 * depth[w]; if (distance != a[i]) { quitf(_wa, "test case %d: required distance %d is incorrect", tc, i); } } } if (!ouf.seekEof()) { quitf(_wa, "extra tokens in the output"); } quitf(_ok, "all test cases are valid"); } 39:T4a1,For a nonempty buyer set $S$, let $m=\max_{i\in S} b_i$, and choose a buyer $r\in S$ with $b_r=m$. Let $P(m)$ be the set of all items with price at most $m$. Buyer $r$ can buy every item in $P(m)$ except possibly their own item. Therefore, $N(S)$ is either all of $P(m)$ or $P(m)$ without item $r$. If no item is missing, every buyer in $S$ has budget at most $m$. Writing - $B(x)$ for the number of buyers with budget at most $x$; - $A(x)$ for the number of items with price at most $x$, we get $$ |S|-|N(S)|\le B(m)-A(m). $$ It is enough to check $m=b_i$. For such an $m$, taking all buyers whose budget is at most $m$ gives deficiency at least $B(m)-A(m)$. If one item is missing from this set's neighborhood, the deficiency is one larger, and that situation is included in the second case below. Suppose item $r$ is missing. Then $a_r\le b_r$, and every other buyer in $S$ must have budget strictly smaller than $a_r$; otherwise that buyer could buy item $r$. Hence $$ |S|-|N(S)|\le 2+B_{<}(a_r)-A(b_r), $$ where $B_{<}(x)$ is the number of budgets strictly smaller than $x$. Taking buyer $r$ together with all buyers whose budget is smaller than $a_r$ reaches this bound.3a:T87e,#include #include "testlib.h" using namespace std; string lowercase(string s) { for (char &c : s) { c = static_cast(tolower(static_cast(c))); } return s; } int main(int argc, char* argv[]) { registerTestlibCmd(argc, argv); int t = inf.readInt(); for (int tc = 1; tc <= t; tc++) { int n = inf.readInt(); int m = inf.readInt(); vector position(n + 1); for (int car = 1; car <= n; car++) { position[car] = car - 1; } for (int i = 0; i < m; i++) { int x = inf.readInt(); int y = inf.readInt(); position[x]--; position[y]++; } vector expectedOrder(n, -1); bool possible = true; for (int car = 1; car <= n; car++) { int p = position[car]; if (expectedOrder[p] != -1) { possible = false; } else { expectedOrder[p] = car; } } string verdict = lowercase(ouf.readToken()); if (verdict != "yes" && verdict != "no") { quitf( _wa, "test case %d: expected Yes or No, found '%s'", tc, verdict.c_str() ); } if ((verdict == "yes") != possible) { quitf( _wa, "test case %d: the reported feasibility is incorrect", tc ); } if (possible) { for (int i = 0; i < n; i++) { int found = ouf.readInt(1, n, "p_i"); if (found != expectedOrder[i]) { quitf( _wa, "test case %d: position %d should contain car %d, found car %d", tc, i + 1, expectedOrder[i], found ); } } } } if (!ouf.seekEof()) { quitf(_wa, "extra tokens in the output"); } quitf(_ok, "all test cases are correct"); }3b:T47a,Let $k$ be the number of red balls among the first $n$ positions of the original row. Because the whole string contains $n$ balls of each color, the last $n$ positions contain exactly $k$ blue balls. Every red ball in the first half is to the left of every blue ball in the second half. Therefore, we can pair these $k$ red balls with those $k$ blue balls and remove all pairs. What remains in the first half is blue, and what remains in the second half is red, so $k$ operations are sufficient. Now suppose that fewer than $k$ operations are performed. Each operation removes only one red ball, so at least one of the $k$ red balls from the first half remains. Similarly, each operation removes only one blue ball, so at least one of the $k$ blue balls from the second half remains. The remaining red ball is still to the left of the remaining blue ball, so the required order has not been reached. Thus, the answer is exactly the number of `R` characters among the first $n$ characters of $s$. The time complexity is $O(n)$ per test case, and the total time complexity is $O(\sum n)$. The memory usage is $O(1)$ apart from the input string.1b:["$","div",null,{"children":[["$","$L35",null,{"contestId":"6a72b7f0d9756e200e2a1bf0","contestNumber":20,"contestUrlId":"20","initialIsRegistered":false}],["$","$L36",null,{"contest":{"contestNumber":20,"title":"Repovive Premier Round 7","startDate":"2026-08-23T14:35:00.000Z","endDate":"2026-08-23T17:05:00.000Z","urlSlug":"$undefined","problemDisplay":"letters","requiresPremium":false,"lobbyProblemsCount":7,"isProblemSet":false,"contestType":"cp","adminOnly":false,"isWeeklyChallenge":false,"weekNumber":"$undefined","ratedMaxTier":"$undefined","announcements":[]},"problems":[{"_id":"6a8747617ac4f2b381fc747c","contestId":"6a72b7f0d9756e200e2a1bf0","slug":"three-at-the-top","title":"Three at the Top","description":"You are given a permutation $p_1,p_2,\\ldots,p_n$.\n\nYou must color every position with one of three colors: red, green, or blue.\n\nA coloring is called valid if the following condition holds for every subarray of length at least $2$:\n\n- the positions containing the largest and the second-largest values in the subarray have different colors.\n\nThe score of a valid coloring is the number of subarrays of length at least $3$ in which the positions containing the three largest values have pairwise different colors.\n\nFind the maximum possible score of a valid coloring.","constraints":"- $1 \\le n \\le 2 \\times 10^5$\n- $p$ is a permutation of $1,2,\\ldots,n$","difficulty":"hard","order":10,"label":"G","releaseDay":"$undefined","points":3500,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"1\n1\n","expectedOutput":"0\n","isSample":true,"hidden":false,"explanation":"There is no subarray of length at least $3$, so every valid coloring has score $0$.\n"},{"input":"4\n2 1 3 4\n","expectedOutput":"2\n","isSample":true,"hidden":false,"explanation":"Coloring positions $1,2,3,4$ red, green, blue, red is valid. The subarrays $[1,3]$ and $[2,4]$ contribute to its score.\n\nIn every valid coloring, positions $1,2,3$ have pairwise different colors. Position $4$ must differ from position $3$, so at least one of $[2,4]$ and $[1,4]$ cannot contribute. Therefore, a score greater than $2$ is impossible.\n"},{"input":"5\n1 2 3 4 5\n","expectedOutput":"6\n","isSample":true,"hidden":false,"explanation":"Color the positions red, green, blue, red, green, in this order. This coloring is valid, and every subarray of length at least $3$ contributes to its score. There are $6$ such subarrays, so no larger score is possible.\n"}],"sampleCount":3,"inputFormat":"$$$\n\\begin{array}{l}\nn \\\\\np_1 \\quad p_2 \\quad \\cdots \\quad p_n\n\\end{array}\n$$","outputFormat":"$$$\nans\n$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":2,"attemptedCount":4,"tags":["combinatorics","greedy","data structures"],"learnPages":[{"title":"Pairs that can become the two largest values","content":"For positions $i\\min(p_i,p_j)\\}|$.\n\nThe values at $i$ and $j$ are the two largest values of some subarray exactly when $d(i,j)=0$. Indeed, if this condition holds, they are already the two largest values of $[i,j]$; if it does not hold, every subarray containing both positions also contains a larger competing value between them.\n\nConsequently, validity is equivalent to requiring different colors at the endpoints of every pair with $d(i,j)=0$.\n\nWhen position $i$ is the endpoint with smaller value, the only such larger endpoints are the nearest greater position to its left and the nearest greater position to its right. This already shows that the constraint graph has only $O(n)$ edges."},{"title":"Which subarrays depend on our choices?","content":"$37"},{"title":"The backbone of every valid coloring","content":"Let $L_i$ and $R_i$ be the nearest positions with values greater than $p_i$ on the left and right. Put position $i$ in the backbone when $L_i$ or $R_i$ does not exist.\n\nThese positions are exactly the union of prefix maxima and suffix maxima. Write them in positional order as\n\n$b_02$, at least one value equals $1$; otherwise the sum would be at least $2k$. At least one value is greater than $1$ as well; otherwise the sum would be only $k$.\n\nConsequently, somewhere in the cyclic sequence a value $1$ is immediately followed by a value greater than $1$.\n\nLet the corresponding consecutive vertices be $x,y,z$, with required distances\n\n$dist(x,y)=1$ and $dist(y,z)=b>1$.\n\nAdd the edge $(x,y)$, remove $y$, and replace these two requirements with\n\n$dist(x,z)=b-1$.\n\nThe new value is positive, and the total decreases by exactly $2$. Thus the invariant becomes $2((k-1)-1)$ for the smaller instance."},{"title":"Reconstructing the tree","content":"Suppose the smaller instance has already been constructed. Attach the removed vertex $y$ to $x$ as a leaf.\n\nThen $dist(x,y)=1$. Also, every path from $y$ to a remaining vertex starts with the edge $(y,x)$, so\n\n$dist(y,z)=1+dist(x,z)=1+(b-1)=b$.\n\nTherefore both removed requirements are restored, while every other requirement stays unchanged.\n\nWhen only two vertices remain, their two stored values are positive and sum to $2$, so both are $1$. Connect those vertices directly.\n\nEvery added edge joins two vertices that are adjacent in the current polygon. It lies on the boundary of that polygon, while all later edges lie inside the polygon of the remaining vertices. Hence no two constructed edges cross."},{"title":"Linear implementation","content":"Maintain the live vertices in a cyclic doubly linked list.\n\nLet `next[x]` be the next live vertex and let `w[x]` be the required distance from `x` to `next[x]`. A vertex `x` is a candidate when\n\n`w[x] = 1` and `w[next[x]] > 1`.\n\nStore candidates in a queue and discard stale entries lazily. When processing a valid candidate, let `y = next[x]` and `z = next[y]`. Add $(x,y)$, delete $y$, set `next[x] = z`, and set `w[x] = w[y] - 1`.\n\nOnly `x` and `prev[x]` can change their candidate status, so only these vertices need to be pushed again.\n\nEach vertex is deleted once and creates only a constant number of queue entries. The time complexity is $O(n)$ per test case, and the memory complexity is $O(n)$."}],"hasLearnContent":true,"likeCount":11,"neutralCount":0,"dislikeCount":2,"isInteractive":false,"interactor":"$undefined","hidden":false,"sampleTestCases":"$undefined","samplesDiverged":"$undefined","sourceAttribution":"$undefined","source":"$undefined","validatorSource":"$undefined","correctSolution":"$undefined","generators":"$undefined","genDataContent":"$undefined","readiness":"$undefined","linkedBuildSessionId":"$undefined","isLinked":"$undefined","authors":[{"_id":"692eca62f11e323ac6f94d25","name":"AmirMohammad Shahrezaei (AmShZ)"}],"statementOverrides":"$undefined","createdAt":"2026-08-20T18:33:19.703Z","updatedAt":"2026-09-04T06:37:54.747Z"},{"_id":"6a87499f7ac4f2b381fc7484","contestId":"6a72b7f0d9756e200e2a1bf0","slug":"density-two","title":"Density Two","description":"There are $n$ points on a number line. Point $i$ is located at coordinate $a_i$.\n\nFor each point $i$, you must choose a closed interval $I_i=[l_i,r_i]$ with integer endpoints. The length of this interval must be exactly $a_i$, and it must contain the point located at coordinate $a_i$. In other words, $r_i-l_i=a_i$ and $l_i \\le a_i \\le r_i$ must both hold.\n\nFor a real number $x$, define its density $d(x)$ as the number of intervals whose interior contains $x$:\n\n$$\nd(x)=\\left|{i \\mid l_i

APair Deletion	500	108/111
BTimeless Overtakes	1000	67/74
CNo Self-Purchase	1500	43/54
DDensity Two	2000	20/28
ETree on a Polygon	2500	14/17
FPerfectly Hidden	3000	3/6
GThree at the Top	3500	2/4