pp

NO you didn't

LL

That's why I am still CPing after getting $$$-35$$$ and $$$-8$$$ in a row. (Got $$$+4$$$ is the last contest :))

100% actually, even tourist

help me also!!

-297 in the last 4 contests xD

Leave CF. Go to LC and atc spend 3 months solving mediums and A-D (on atc) there, and when you come to CF stop solving 800-1000, push yourself, gl

I am not caring about rating for now, for now my goal is to get full grasp of $$$D$$$ as soon as possible so that I can become yellow fast

Binary search is possible but not necessary. This can be solved in O(n)

N is only 2000 so i was tired with it and decided to go "Fk it" and yolo with O(N^2).

> inb4 "O(N) exist", I know but I'm too tired with B and I just want to get over with it.

I was able to solve black circle pretty fast that time this one was hard for div2 A

Not quite, B is just tricky

no, the constraint has k<=1414, hinting a factor of root of 2 occurred someherewhich gives an hint towards the formation of square with side length = min(x,y)

Actually, the constraints are on X,Y and K in each test case, not on the sum of them over all test cases. So time complexity of O(XY) (or something else that is second order) requires a worst case of 1000*1000*5000 calculations, exceeding the time limit

I feel like you either observe the solution instantly for A or you don't at all.

B is a standard problem, and it took me nothing to figure out the solution.

It's just some prefix sum stuffs

prefsums + binary search. you can check my sol https://mirror.codeforces.com/contest/2026/submission/288582700

(assuming 1-based indexing everywhere) consider the b array as divided into blocks as this: (n size block) (n — 1 size block) (n — 2 size block)..... now consider one block which has starting element of pair as i. what is the sum of this block? s(i, i) + s(i, i + 1) + s(i, i + 2) + ... s(i, n) where s(l, r) is sum of a from l to r. you will see that in this expression, a[i] is added n + 1 — i times. so calculate suffix array on a[i] by this rule (a[i] * (n + 1 — i))

now if i want sum of k blocks, i need sum of block 1, sum of block 2, ... sum of block k i.e. suff[1] + suff[2] + .... suff[k] so create a prefix array on the suffix array created before.

now consider this problem: we want to find sum 1 to x, in array b:

first find number of blocks that are completely covered say k — 1 (use binary search) add pref[k — 1] then we are at block k, now if this block has l as left point of the pairs. we want to find (l, l) + (l, l + 1) +.... (l, l1) (l1 depends on where x lies in this block. now for this we can add suff[l] — suff[l1 + 1] directly. but note : this followed rule (a[i] * (n + 1 — i), but now a[i] has not been added (n + 1 — i) times. you will see that now a[i] has been added (n + 1 — i) — (n — l1) times. so you need to subtract s(l, l1) * (n — l1). again have a prefix array on original a for this say this answer we calculated for sum of b from 1 to x, is given by f(x), then given query is answered by f(r) — f(l-1).

me too, but why them work?

Why is div2E max flow :(
I hope there are simpler solutions

Thanks, can you give a case where the picking the either last or first doesn't work for odd n? I couldn't come up with such a case

why return cnt >= n/2;

how you got this idea?

Solution can be seen here : https://pastebin.com/WyE4dwSL

after the first WA2, i waste about 50mins. at WA5 bcos i were minimizing the ans with 1e15 :(