is there team participation?

fixed

Nope

It's a Russian olympiad. You didn't upvote?

In addition, there is a Leetcode contest at the usual time of codeforces rounds.

Hard like the most of unusual time contests but the standing will be much greater then other rounds so rating will also increase more then other contests. Point to think! And Wishing good luck to you all

For gray users all the rounds (expect Div.1, because you can't register for it + some rounds like april fools contest) are rated.

There is olympiad in this time, round based on it. The unusual time is to avoid cheating

There's also a codejam round on the usual time.

First,it's rating.It's because they would like to practice since there is no div.1 for it.

Nice quote...

Nice bro!

edge cases ?

saw your dp solution of c question , edu round :) love u bro

You can find contribution of each subarray.

Let us focus on some subarray $$$s$$$. There exists a mask $$$m$$$ for $$$s$$$ such that $$$s$$$ will contribute to the answer iif mask of query is supermask of $$$m$$$.

$$$m$$$ gets fixed because we have the restriction that if $$$s[l] != ?$$$ and $$$s[r]=?$$$, $$$s[r]=s[l]$$$ ($$$r=|s|-l+1$$$).

Now for subarray $$$s$$$ to contribute $$$1$$$ to the answer, some $$$?$$$ get fixed and rest $$$?$$$ are flexible. Suppose we have $$$freq$$$ flexible $$$?$$$. Finally $$$s$$$ will be contribute $$$1$$$ to answer in $$$|t|^{freq}$$$ arrays.

Segment tree has a much bigger constant than Fenwick tree

maybe you can use int instead of long long

and use scanf/printf instead of cin/cout

You’ve made the ST too big. Much bigger than required.

you don't have

cin.tie(0)->sync_with_stdio(0);

you shouldn't use 'build' initially all values ​​are 0

Why do you use long longs?

sum() uses loop internally

Which tasks required segment trees? I only looked at A, B, C and D and none of them required it (or anything similar like Fenwick)

I use segment tree with lazy propagation.

You can use a data generator.

If you have at least one rock in a row set the row's value to 1. If you you have at least one rock in a column set the column's value to one. Now you wanna know if the sum of the columns in [x1,x2] is exatly x2-x1+1 or if the sum of the rows in [y1,y2] is exactly y2-y1+1. This can be easily done with a segment tree

Think of a way to maintain the empty rows/cols, after that when they ask you to check the subrectangle try to find if there is a row and a col that is empty and satisfy this condition: x1 <= row <= x2 && y1 <= col <= y2, if you found such a row and a column then the answer is no otherwise the answer is yes

When a rook is inserted on (r, c) notice that it covers all cells on row r and col c

Let's store for each row if it's already covered by a rook Do the same for columns

Now the subrectangle queries ask if for each cell, either their row or their col is covered

A subrectangle query consider a range of rows and cols

What happens if a column is not covered ? Basically you need all the rows to be covered for the cells of this column to be covered

(same argument in reverse)

This way we show that the answer is "Yes" iff all the rows or all the cols are covered

Let's say we put a 1 when a row is covered

We just need to range sum over the range of rows and make sure the sum is equal to the length of the range

Same for cols

To handle rooks removal, we count for each row the number of rooks covering it

When this count reaches 1, we add one in our segtree/bit

When it reaches 0, we add -1

Code: 157157585

The idea for D is fairly simple (and a good learning exercise if you aren't familiar with the "trick"). You just need to combine 3 independent pieces: Binary Search on answer, Cycle detection and Longest path in DAG.

Since we are asked to minimize the maximum value of some quantity, it's natural to think in terms of binary search. However, this can be a trap if the function is not monotonic. To work around it, a clever way to define the predicate is to use the at least keyword. Instead of asking whether an answer with value val exists, we ask

Does an answer with value at least val exists?

With this keyword, it's fairly obvious that existence of at least val implies the existence of at least all value less than val as well.

To verify a predicate, you can ignore all vertices with value > val while performing a DFS. (You might've seen this in problems asking you to find the maximum value less than threshold on a path between 2 vertices in a tree). After ignoring these vertices, if the resulting graph contains a cycle, it means you can travel it infinitely many times. If not, it is a DAG. Then, you just need to find the longest path on this DAG and verify if it's at least $$$k - 1$$$.

Note that you can do all of this in a single DFS (and without explicitly creating the new graph).

Code

Binary search for the answer. And for each check, we could search for cycle or a longest chain in the new DAG, which we needn't really create a new graph but just judge the number on each vertex

What exactly D asks for?

We can use binary search to find the answer.

When we are checking if there exists a path of length k with nodes whose values are less than or equal to 'x'(current binary search value), we consider the subgraph 'C' formed by the nodes whose values are less than or equal to 'x'. Now we have two cases. 1. There is a cycle in this subgraph C, the answer is true for this x in this case. 2. There is no cycle => subgraph is a DAG. Find max path length using DP and check if the max path length is >= k. The answer is true for this x if that is the case.

Steps 1, 2 are of O(n) complexity each. We do them for a total of O(log(max(a[i]))). Therefore total complexity is O(n*log(max(a[i]))). code.

The max number of cars is calcualted using the maximum number of 4 wheel cars. The min number of cars is calculated using the maximum number of 6 wheel cars. We need to consider some edgecases, like odd numbers.

isn't E

?

me too :( let's be more patient

I guess tot = b[1] * n is $$$O(n)$$$

Yeah this is frustrating. It's only a single linear loop. https://codeforces.com/contest/1679/submission/157146581

I also tried the standard Python 3, it just barely passes the pretest but of course it is TLE again on the system test

how to solve d?

I didn't solve it but I tried solving it by considering a "loop" to be equivalent to a "cycle". Is it not the case?

The common wording at least on codeforces is that a loop is a self-loop, a edge that starts and end at same vertex, so a cycle of length 1.

And a cycle is a circular path containing more than one vertex.

(https://en.wikipedia.org/wiki/Loop_(graph_theory))
(https://en.wikipedia.org/wiki/Cycle_(graph_theory))
just check out these links, it's not codeforces-related terms but common ones

Yes! You can read about it right here

hint: keep timestamp of modifing for each item

Someone really wrote seg tree there?)

Store the initial sum in s.No need to store the array.Maintain a map instead of all the type1 changes made to the array after the recent type2 operation.Maintain a variable l initialized to 0, to store the x value of the last type2 operation.So everytime you get a "1 i x" just look into the map if some change was registered at pos i by "m.count(i)", if it's not zero then update s as s+=x-m[i], else if no change was registered the cell contains the last type2 change hence s+=x-l.Now when you encounter type2 operation clear the map and update the variable l to the new x and the sum s to n*l. Link to my not so legible code

it got me too :(