На месте

присутствуют

Maybe he implies that the problems are not sorted by difficulty

Держи в курсе

and also not a geometry one!

I like mathforces

who cares about you to be honest

Не жду задачу А

Seems so, coz his problems are generally based on good idea/observation + quick/short implementation but if you haven't thought of the idea clearly then implementation can go pretty lengthy and fail on system tests

I think you should block both users

The number will obviously fit.

E can be solved with segment tree + lazy propagation.

2nd query will be discarded (just calling the get function).
To do the 1st query, first update that single element without lazy propagation, then perform updating all elements id in the range [i + 1, mx] (inclusive) with , with mx as the maximum index that . mx could be found by binary search.

Tried to create a difference array from array A and array K, and tried updating the values of this diff array for query of type 1, it will turn most of the values of this diff array to 0.

Query of type 1 will increase the diff value of only first element and make all other diff value 0. So, at most 2*n values need to be updated at most.

Tried to maintain the index of non-zero values of this diff array using set,and then range update and range sum query using segment tree lazy propagation.

The answer will fit inside of a long long. max(A) starts out  ≤ 10⁹ and you can add at most 10¹¹ to it, so A[i] will at most be around 10¹¹, meaning the sum of the As will at most be around 10¹⁶. So everything should fit inside a long long without any problems.

About the solution: You can reduce the problem to all k being 0 by working on instead of A. For B we have that B[i] ≤ B[i + 1] so it must always be increasing.

To do the two types of queries I used binary search together with a lazy segment tree that allowed sum on intervals and set on intervals.

To do the add query you need to add x to B[i] and then update the rest of B so that it is increasing, to do this you can apply binary search on B to find all indices j such that j > i and B[i] > B[j]. Then use the set on interval operation to make all of those B[j] equal to B[i]. This takes per query.

To do the sum query just use the built in sum in the lazy segment tree. But this is a sum over B and not A, so you need to adjust the answer by removing the extra k you added in the beginning, which can be done by playing around with cumulative sums. This takes per query.

There is a solution that do not uses segment tree tricks, just two plain seg trees, one with range += lazy and range sum other with range = and one get one element.

You can notice that if you update a[i] += x that leads to a[i + 1] = a[i] + k[i] and so on from i to some l, than if you'll update a[i] += y again, you'll just make += on range(i, l). So this observations leads us to smth like DSU (disjoint set union). But there is one thing, when we get query update a[i] += x and i belongs to some [l, r] segment where l is strictly less than i this segment [l, r] splits to two [l, i — 1], [i, r]. So you need to do unusual DSU with segment tree (the one with range=).

When you get a[i] += x query your steps is split range to which i belongs than go to right and merge some ranges (continue while conditions from statement is true), while merging make += on right range. It is clear that we will do at most n + q mergins, because we can merge only by two reasons 1 — it was originally disjont (thats n) or 2 — it was splitted (that's q). Complexity O((n + q) * log(n))

Submission for details 51198410

You can solve it using plain segment tree with lazy updates.

Notice the fact that the values will be increasing. So, suppose that the i+1 th index is changed once due to the update on i'th index. Now, if somehow a[i] increases again, a[i+1] will increase by the same amount. Based on this, you can perform range updates. And number of these updates won't be that much.

If you can swap, do it immediately otherwise take the previous pupil to the farthest position from you, until nothing change

We will iterate from the back of the queue (person before Nastya) to the front. We will store for each person i how many persons are after this person in the queue and are favored by person i, in fav[i]. Initially we set fav[i] for each person i that favors Nastya to 1. We will also maintain a variable that stores how many persons have been removed from the queue so far. Now if we are at person i and there are x persons removed, a total of rem = n - 1 - i - x persons remain to the right of this person. If fav[Q[i]] == rem, every person that remains to the right of this person is favored by this person, and thus this person can swap with each one of these. In this case we remove this person and increase our answer by 1. Otherwise we cannot remove it and we will increase fav for all the persons that favor this person.

The complexity of this approach is O(N + M). https://mirror.codeforces.com/contest/1136/submission/51189237

I just pushed every person that can let Nastya stay before him to the end of p[] (to the place before such persons that are already at the end), and then counted number of such persons in the end of p[].

Observation: if person can not be pushed to the end, he can not ever let Nastya ahead.

51192297

Moving from natasha to first guy, if you find the guy that can move to back of natash,then move it.

Each respective diagonal in the matrix must have the same elements.

Notice that you can imitate transposition of every matrix by little transpositions of matrices 2x2. That's because transposition of matrix 2x2 swaps two nearby elements on the diagonal, and transposition of matrix nxn swaps some elements on every it's diagonal (elements that are on a diagonal remain on that diagonal). But you can imitate every permutation by some swapping nearby elements.

I noticed that transpose does not change the sum of row+column. That's why I just verify that both matrices have values with equivalent sums. I did not prove it though.

Each respective diagonal in the matrix must have the same elements.

Check in your "Compiler settings" if you'd enabled C++11 features yet.

setting -> compiler -> c++14 ->OK

Yeah. My stupid bugs failed only on 21th pretest. It's was awful

Any idea what the hacks were for problem C ??

He definitely will be disqualified.

How did he manage to get 7 fake accounts in same room?

They think good rating makes them look cool xD so silly

I care about my rating just because that means I have improved

apparantly I_love_sad_crying_cats noticed this during the contest and got benefited with bb2211's kid play ;) Lol..well played I_love_sad_crying_cats !

*pretests

I got. Very stupid mistake. the amount of diagonals is n + m -1, isn't 2 * n-1. With this mistake my solution broken down only on 72 test.

it just passes on re-submission. once with 19ms gap and once only 4. Server tends to have some measurement error for different run of tests depending on processing load and bunch of other stuff. Check https://mirror.codeforces.com/blog/entry/49965#comments for more info.

how it is done , how to skip a solution . As far as i know , if u want to skip a solution , submit same solution from different account , codeforces will give u system warning and ur solution will be skipped , but if this continues to 2 or more times ur accnt will be blocked ? am i right MikeMirzayanov

We claim that the optimal construction is as follows.

Maintain a "bubble list", which initially contains only Nastya. Then, iterate through every person in line, starting with the one directly in front of Nastya. If this person can be passed by every person in the bubble list, then move them back until they're behind Nastya and increment the answer by one. If there is a person in the bubble list who cannot pass the current pupil, add the current pupil to the bubble list.

Clearly, this construction is valid given the problem parameters. To prove that it is optimal, suppose that there is some pupil A who cannot be passed by some person B, who himself cannot get behind Nastya in the line. No move except for B directly passing A will put B in front of A, so A cannot get behind B, meaning A cannot get behind Nastya. So, any person who cannot be passed by someone in the bubble list cannot get behind Nastya no matter what sequence of moves we use. (To formalize this argument, we'd need to use induction, since we implicitly assume that the bubble list is "correct" before processing each pupil.)

In terms of efficiency, iterating through every pupil is O(N). Checking to see if a pupil can be passed by everyone in the bubble list is O(N) in the worst case, but because there are only M passing pairs, this operation takes only O(N+M) operations. The most intuitive way to check whether one pupil can be passed by another is to use a set or a sorted list, either of which support queries in O(log N). So, the efficiency of our algorithm is O((N+M) log N), which easily passes.

We've already talked about this elsewhere, but I think it's worth adding to the discussion here.

I can't pass the suggested test to your program as input in custom invocation because the file size is too large. But I can fill in your data structures n, m, p, g in the code itself like so here. (See how I'm not reading into n, m, p, g from standard input). (This should be fine because reading input shouldn't be the slowest part of your solution).

This runs in 46ms in custom invocation.

The code does look like it should be O(n^2). Does anyone know why it doesn't TLE on Codeforces? My guess is some compiler optimization magic. :)

Edit: Running the program locally with the input hardcoded results in a similar running time as running the program locally and reading the input from standard input, so I’m not convinced that compiler magic is only because of hard coding the input into the program.

There will surely be many contests in between. Wait for a couple of days, they might not be declared yet.

VivaanGupta have a look now on the contest page. One is declared. Still there can be more contests :)

The same happened to me

I met the same problem.

During the contest, this code got TLE on test 10. Then I changed the range of my arrays from 500 to 5000, and the new submission got AC.

After the contest, I re-submitted the same solution with arrays of range 500 and got AC.

I think the test data before were incorrect, and maybe after the contest, the author corrected them. Why doesn't Codeforces rejudge all submissions of this problem? It's not fair. MikeMirzayanov