Ratings after SMTC2020 and LTIME83B(April Lunchtime 2020) is not updated

snehashis_rock · April 25, 2020, 5:37pm

Ratings after SMTC2020 and LTIME83B(April Lunchtime 2020) is not updated.
Even the graph isn’t showing any participation.

tannatsri · April 25, 2020, 5:38pm

it will take 1 day to get updated.

snehashis_rock · April 25, 2020, 5:39pm

Ok bro, thanks.

nemesis3733 · April 25, 2020, 5:49pm

SMTC was not rated btw

galencolin · April 25, 2020, 5:51pm

Lunchtime is updated now.

nemesis3733 · April 25, 2020, 5:58pm

hey! @galencolin can you share just a brief of your approach for triangle query as the editorial is not released yet?, I thought of processing the queries offline and for each point add 1 to all the all possible triangles it can be in but got a TLE

galencolin · April 25, 2020, 6:13pm

Your solution should work for the first subtask where all heights are the same, but the second subtask is more complicated.

A triangle is uniquely determined by its peak, let this be the point (x_i, y_i). For a point (x_j, y_j) to be contained within the right half of the triangle i, it must be true that (x_j - x_i) \leq (y_i - y_j), and therefore x_j + y_j \leq x_i + y_i. You can derive a similar formula for the left side. All that remains is to efficiently count points where x_j + y_j \leq x_i + y_i for all i, which can be done with sweepline and pdbs or a fenwick/segment tree.

Be careful with overcounting on even lengths. I spent almost 2 hours struggling with that

nemesis3733 · April 25, 2020, 6:42pm

Got it now bro thanks alot , also congrats for hitting 6 stars