DishonoredRighteous's blog

By DishonoredRighteous, history, 4 days ago, In English

Hello, Codeforces!

I'm glad to invite you to Round 791 which will start at May/14/2022 12:35 (Moscow time). Please notice the unusual time.

There will be 6 problems in the round. Round is based on Team Olympiad in Lipetsk which is being held for the seventh time. Problems were proposed and prepared by iakovlev.zakhar, Kon567889, iura, andr1y, Masha237, welleyth and me. I would like to thank Aleks5d and KAN for CF round coordination and testers: Um_nik, 353cerega, errorgorn, Stepavly, divanik, nnv-nick, 4qqqq, to be continued...

Of course, I'd like to thank all Codeforces team for Codeforces and Polygon beautiful platforms!

I also would like to thank golikovnik, egneeS, dshindov and Inessa Shuykova (Lipetsk teams' coach) for preparing other Olympiad problems that haven't been taken for this round.

Note that if you are an official participant of the Olympiad, you are not allowed to participate in this round.

Scoring distribution will be announced later.

Wish you good luck and high rating!

UPD.1 Scoring distribution: $$$500 - 1000 - 1500 - 1750 - 2250 - 3000$$$.

UPD.2 Congratulations to winners!

Official participants:

  1. xiaoziyaooo

  2. StickyFingers

  3. mybing

  4. huangweiliang

  5. NewPC2022

Unofficial participants:

  1. SSRS_

  2. leaf1415

  3. uwi

  4. maspy

  5. DeadlyPillow

UPD.3 Editorial is available here.

 
 
 
 
  • Vote: I like it
  • +225
  • Vote: I do not like it

»
4 days ago, # |
  Vote: I like it -17 Vote: I do not like it

Team based round... interesting, will participate.

»
4 days ago, # |
  Vote: I like it +42 Vote: I do not like it

Users rated >= 2100 can't seem to register for the round?

»
4 days ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

I like when contests are at this time. (5:35 AM, Saturday for me) It forces me to not sleep in and be a lazy bum

»
3 days ago, # |
  Vote: I like it +11 Vote: I do not like it

hopeforces

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Will the problems be a different style than regular rounds?

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

i see olympiad i upvote (unless its russian, then i just comment)

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 days ago, # |
  Vote: I like it +60 Vote: I do not like it

CF 791 -> ABC 251 -> Code Jam Round 2

No clashes with 20-25 mins break each. Sweet. Thanks for the unusual time :)

  • »
    »
    3 days ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

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

»
3 days ago, # |
  Vote: I like it -13 Vote: I do not like it

Guys, be careful. Unusual time

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it only me, or does everyone feel that contest at an unusual time has less participation than the usual time contest? Hence have less probability for the rating to increase. I know we should not give contest for rating, but still...

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

This round will be hard. Good luck everybody!!!

  • »
    »
    3 days ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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

»
3 days ago, # |
  Vote: I like it +1 Vote: I do not like it

How to know if a contest is unrated for me, I am new to the cf and could not find any official post on this info yet ?

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks for the info! does that mean div 3 users can participate up to div 2 rounds and also not to div 4 rounds as well?

      • »
        »
        »
        »
        2 days ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        See, as a grey coders can give div, 2, 3, 4, and all of these are rated for them. I think you are trying to think of these contests in terms of CodeChef contest, those two are pretty different.

        • »
          »
          »
          »
          »
          2 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          yeah I see. Thats why I was super confused at first, but the lack of official post on how ratings works on codeforces. I found a old post that explains div 3 but I could not find anything which provides all the information at one place.

»
3 days ago, # |
  Vote: I like it +12 Vote: I do not like it

The unusual time strikes back.

»
3 days ago, # |
  Vote: I like it -8 Vote: I do not like it

Why so unusual time? anyone any idea

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Please add the contest link in the blog.

»
3 days ago, # |
  Vote: I like it -6 Vote: I do not like it

Why the time has changed ? Not great time

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

If the score is more than 2100, why do people with a score of more than 2100 participate in the ranking

  • »
    »
    2 days ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

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

»
3 days ago, # |
  Vote: I like it -14 Vote: I do not like it

"i_am_completely_useless for being completely useless." -- Sakura :))xD

»
2 days ago, # |
  Vote: I like it +9 Vote: I do not like it

Thank you for the unusual time!

»
2 days ago, # |
  Vote: I like it -8 Vote: I do not like it

excited for this contest, go go go !

»
2 days ago, # |
  Vote: I like it -8 Vote: I do not like it

My First CF Contest! Woohoo!

»
2 days ago, # |
  Vote: I like it -8 Vote: I do not like it

Unfortunately, I need classes at that time, so I can't participate in this contest.

»
2 days ago, # |
  Vote: I like it -10 Vote: I do not like it

QueryForces

»
2 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Pretests in C must be extremely weak

  • »
    »
    2 days ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    edge cases ?

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      first q/2 queries of type 1 having x = i , y = i for i 1 to q/2

      Then next q/2 queries of type 3 having x1 = 1 , y1 = 1 , x2 = n , y2 = n .

      If somebody checked type 3 queries linearly from x1 to x2 , or y1 to y2 then Complexity will be O(Q*N) and there are many such accepted solutions

»
2 days ago, # |
  Vote: I like it +11 Vote: I do not like it

waiting for contest finish to get solution for problem E

  • »
    »
    2 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    2 days ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    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.

    • »
      »
      »
      2 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      There are $$$2^{17}$$$ masks, and len $$$|t|$$$ is up to 17, and also we need to sum up all summasks foreach mask.

      All my tries did run like more than a minute...how to do that right?

      • »
        »
        »
        »
        2 days ago, # ^ |
        Rev. 2   Vote: I like it +7 Vote: I do not like it

        Say mask of query is $$$q$$$.

        Now you need to check contribution of all masks $$$m$$$ such that $$$q&m=m$$$. You can traverse over all submasks in $$$O(3^x)$$$ operations(here $$$x=17$$$).

        Suppose we have a $$$dp$$$ array, such that mask $$$x$$$ will contribute $$$dp[x][i]$$$ to the answer, if $$$q&x=x$$$ and $$$__builtin_popcount(q)=i$$$. So you calculate this $$$dp$$$ while traversing all subarrays(fixing middle position and moving sideways).

        You can precompute answer for all masks.

        My submission

        • »
          »
          »
          »
          »
          2 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          oh thanks! I forgot about this trick to iterate over submasks

        • »
          »
          »
          »
          »
          2 days ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          actually you can solve it in $$$O(2^{17}\times 17^2)$$$ by using SOS dp or fast walsh transform.The solution is similar to yours.

          My submission

»
2 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why Segment tree solution is giving TLE in C. :(

code
»
2 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Used a single loop in Problem-B, still exceeded the time limit, is it me or python at fault here?

»
2 days ago, # |
Rev. 2   Vote: I like it +33 Vote: I do not like it

Thanks to iura for setting F! I really enjoyed solving it during testing. Here is my alternate solution to F that works for much larger constraints.

Let $$$S_i$$$ be sets containing all representatives of all arrays $$$a$$$ of size $$$i$$$ and $$$C_i$$$ be the set of cliques of size $$$i$$$. When we talk about clique, we are talking about cliques on the graph where we draw the edges as $$$(u_i,v_i)$$$. Also when we talk about arrays, we will basically refer to its equivalence class, so treat $$$a$$$ as the representative.

Take some array $$$a$$$ and let $$$s_a$$$ be the possible values of the first element of $$$a$$$ after some operations. Note that it is necessary that $$$s_a$$$ is a clique because otherwise, we are not able to swap all values in $$$s_a$$$ to the start of $$$a$$$.

Let us suppose that we know $$$S_j$$$ for all $$$j<i$$$ and now we want to find $$$S_i$$$. For all arrays $$$a \in S_{i-x}$$$ and $$$c \in C_{x}$$$,put $$$(c,a)$$$ into $$$T_{x}$$$. That is, we want to think about arrays $$$a \in S_i$$$ as the concatenation of some clique and another array. Unimportant remark: $$$c \subseteq s_{c+a}$$$.

However, the problem with this is that are multiple ways to make a certain array. As a simplest example, consider when we can swap $$$(1,2)$$$ only. To make array $$$[1,2,3]$$$, we can split it into $$$([1,2],[3])$$$, $$$([1],[2,3])$$$ and $$$([2],[1,3])$$$. Of course, we do not want to double count.

Let us consider some $$$a' \in S_i$$$ where $$$k=|s_a|$$$. There are $$$2^k-1$$$ combinations of $$$c+a$$$ that produces $$$a'$$$. Every subset $$$c$$$ of $$$s_a$$$ corresponds to a $$$(c,a)$$$ tuple, and there are obviously $$$\binom{k}{x}$$$ such subsets with $$$|c|=x$$$, so $$$\binom{k}{x}$$$ tuples in $$$T_x$$$ corresponds to array $$$a'$$$.

One can see that $$$|S_i|=|T_1|-|T_2|+|T_3|-\ldots$$$ by looking at the individual term of some $$$a' \in S$$$ and noticing when only considering tuples that correspond to $$$a'$$$, we have $$$\binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \ldots =1$$$ on the right hand side. Note that by definition, $$$|T_x|=|S_{i-x}| \cdot |C_x|$$$.

Let the number of digits be $$$d$$$. If we let $$$ans_i$$$ be the answer for length $$$i$$$, we have the explicit recurrence $$$ans_i=\begin{cases} 0,& \text{if } i < 0 \\ 1, & \text{if } i=0 \\ \sum\limits_{j=1}^d ans_{i-j} (-1)^{j-1}|C_ j| & \text{if } i>0\end{cases}$$$.

We can find all $$$|C_j|$$$ in $$$O(2^d)$$$ by brute force. To do this, we check if some mask $$$bm$$$ is a clique in $$$O(1)$$$ by taking an arbitrary bit $$$b$$$ from $$$bm$$$, checking if $$$bm \oplus b$$$ is a clique and that $$$b$$$ is connected to everything in $$$bm \oplus b$$$. Since we can solve linear recurrence in $$$O(d \log d \log n)$$$, we have total complexity of $$$O(2^d+d \log d \log n)$$$ but it probably does not matter what algorithm we use to solve the linear recurrence since there is no way it is going to dwarf the $$$2^d$$$ term.

Can we find all terms of $$$|C_j|$$$ faster than $$$O(2^d)$$$?

Code: 157227780

»
2 days ago, # |
  Vote: I like it -16 Vote: I do not like it

segment tree forces

  • »
    »
    2 days ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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)

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      B and C were doable using segment trees

      • »
        »
        »
        »
        2 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        My solution to C tle'd using Fenwick tree any suggestions ?

        • »
          »
          »
          »
          »
          2 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          ++ I used segment tree my solution got tle'd too. I don't know where did I go wrong . :(

          • »
            »
            »
            »
            »
            »
            2 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You should use int instead of long long whenever you can. Also it'll be good to use the fast I/O:

            cin.tie(nullptr);
            ios::sync_with_stdio(false);
            

            Finally if it doesn't work, use a fenwick tree as it's constant factor is way better than a segment tree's

        • »
          »
          »
          »
          »
          2 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You can refer my submission: 157174605

          • »
            »
            »
            »
            »
            »
            2 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Hey winterfire can you check my submission and let me know what you think ? submission

            • »
              »
              »
              »
              »
              »
              »
              2 days ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              This solution would get WA even if it didn't TLE. Despite that, you need to use fast I/O. Try adding this:

              ios_base::sync_with_stdio(false); cin.tie(0);

              • »
                »
                »
                »
                »
                »
                »
                »
                2 days ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                Oh lord thanks Restricted I am using this template from a long time never noticed fast i/o wasn't included that's why I was wondering my submission for B took 1.5 sec but is just simple operations..

            • »
              »
              »
              »
              »
              »
              »
              2 days ago, # ^ |
              Rev. 3   Vote: I like it 0 Vote: I do not like it

              I don't know about TLE but why you are modifying the FT every time?

              let's say n number of rooks covering for the ith row! then you don't need to modify FT with -1 unless all the n rooks targeting that ith row are removed! In the same way, you need to modify FT with +1 only when no other rook was targeting that row previously.

              And lastly, your type3 query should also be corrected accordingly otherwise WA (as stated by Restricted)

        • »
          »
          »
          »
          »
          2 days ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          I did it using segment trees. Create two seg trees for handling rows and cols. If a rook is placed/removed at cell x, y then update the xth row and yth col. For query of type 3, if the bitwise AND of rows x1 to x2 > 0 or cols y1 to y2 > 0 then answer exists.

        • »
          »
          »
          »
          »
          2 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Mine passed in 290ms 157157585

          I'll try to see why your sol TLE'd

        • »
          »
          »
          »
          »
          2 days ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          your solution is wrong

          Consider a case with a 5x5 grid

          RRRR.
          R....
          .....
          .....
          .....
          

          If I query on the whole grid, the answer should be No but your code will output Yes because you shouldn't add 1 everytime you place a rook. See my explanations here for more details:

          • »
            »
            »
            »
            »
            »
            2 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks bestial I got it its wrong , I think TLE is because of fast i/o but if you see any other issue with BIT implementation let me know

            • »
              »
              »
              »
              »
              »
              »
              2 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              It seems ok but for more safety I would add ++index b efore computing any answer for queries (this is because the bit trick you use doesn't work for 0). Adding the ++index would allow you to use the BIT like it's 0-indexed if you want. You only need to make sure that you allocate extra memory but you already did that :)

      • »
        »
        »
        »
        2 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes ofc you can use segment trees as arrays

      • »
        »
        »
        »
        2 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        however actually B can be solved in $$$O(n+q)$$$ without using segment tree

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Maybe B and C.

»
2 days ago, # |
  Vote: I like it +6 Vote: I do not like it

n = 2 should have been in the samples in A :(
Btw, I wonder how many people solved B using segment tree

  • »
    »
    2 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I use segment tree with lazy propagation.

    • »
      »
      »
      2 days ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      You can do it in an easier way.

      You want to perform three types of queries

      • set all the elements to x

      • change the value of an element

      • compute the sum of the array

      If you don't have the "set all the elements to x" queries, you can just compute the sum at the beginning and when you change the value of an element you know how the sum will change.

      The only problem is that if you performed a "set all the elements" query, the value of the element might not be the one you stored in the array.

      To handle this, notice that the latest query will give the value of the element.

      So you just keep track of the time when the set query was applied and when the change query of each element was applied.

      Code: 157146130

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Overkill. Could be easily solved in O(n + q) via storing the last occurrence of updating the whole array and the last occurrence of updating an index for each index.

»
2 days ago, # |
  Vote: I like it +7 Vote: I do not like it

I tried to hack C with 2e5 queries and it said input cannot exceed 256kB, what T_T

  • »
    »
    2 days ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    You can use a data generator.

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Will learn how to use that before the next contest, till then pain

      • »
        »
        »
        »
        2 days ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Hacking with a generator is quite simple. Just output the test case you want.

        For example, a test generator for B

        Some things to note are: Don't output any extra spaces or blank lines (e.g. after arrays), and the test case should always end with an endl character (e.g. cout << n << '\n'; instead of just cout << n;). Basically you should follow test standard practices strictly.

»
2 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

how to solve c ? some one pls tell me your approach :* (i've tried to do it with brute force by making maps in the last 10 min I was knowing that it gonna get me tle :D ) so how can we solve it:*

  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      hey bro just need a favor from you basically you are a specialist you might be having a good idea about cp so can you tell me after seeing my profile and rating that should I learn segment tree or not cause some of my seniors were saying to me that to learn segment tree your rating should be at least 1500 or something but from last few contest I'm seeing that there is one question of segment tree between a,b,c and you might remember that div4 contest which just held few days ago in it also h2 problem was solved using segment tree so can u suggest me,that when should I learn about it or i should wait for few months :*

      • »
        »
        »
        »
        2 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't see why not. It's not that hard of a concept and it makes you understand some other CP concepts better. At least know what it does and how to use it.

      • »
        »
        »
        »
        2 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You should learn to use ordered set. Today's C and div4's H2 could be easily done with ordered set.

        • »
          »
          »
          »
          »
          2 days ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          but in java there is nothing as ordered set:* can u suggest any alternative:D

          • »
            »
            »
            »
            »
            »
            34 hours ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I don't think there is any alternative in java. You have to use fenwick or segment trees.

  • »
    »
    2 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I solved it using sets and binary search

      • »
        »
        »
        »
        2 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        but how who can we find it with bs:* can u elaborate

        • »
          »
          »
          »
          »
          2 days ago, # ^ |
            Vote: I like it +2 Vote: I do not like it

          Here's my solution https://codeforces.com/contest/1679/submission/157198959

          The idea is to keep track of the empty rows and empty cols, initially everything is empty so we will insert into our rows and cols the numbers from 1 to n;

          Rows = [1,2,3,...n] Cols = [1,2,3,...n]

          Now anytime we insert a rock to some (r,c) that means the row is no longer empty and the col is no longer empty, so we will remove r from our Rows set and c from our Cols set.

          Now, how can we know that this row/col is empty? we can keep track of the rocks count in each row and col, once the count for a row/col becomes 0, this means we need to insert it into the corresponding set.

          Take a look at my solution, and hopefully, you will understand what I mean.

          • »
            »
            »
            »
            »
            »
            2 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I tried something like that but there was something wrong and it TLEd on somewhere near the 40th case.

            • »
              »
              »
              »
              »
              »
              »
              2 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I got TLE first and then used fast I/O and it worked

      • »
        »
        »
        »
        2 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I used Ordered Set to solve C.

  • »
    »
    2 days ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D? My idea is to go through the nodes in increasing order and activate them one by one. Once I activate them I want to know if a strongly connected compononeted is activated, this means that I am done regardless of what K is. This is easy to do. The hard part was knowing whether a path that is K long in is created. How do you do it?

  • »
    »
    2 days ago, # ^ |
    Rev. 2   Vote: I like it +43 Vote: I do not like it

    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

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Of course you do binary search how did I miss it. Eeh, I feel so dumb haha. Thanks a lot!

      • »
        »
        »
        »
        2 days ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        You don't need to feel dumb, it happens not to be able to solve a problem!

        What you should learn from this is that problems asking to minimize the maximum (or maximize the minimum) can be solved with binary search in 99% of the cases because fixing the max/min gives you a smaller structure where you have complete freedom (for example in this problem, you don't have to care anymore about whether you move on a too big node)

        You can find some similar problems on usaco guide:

        Wormhole Sort

        MooTube

        • »
          »
          »
          »
          »
          2 days ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          That's so nice of you to say thank you! I will definitely be checking the problems you suggested later.

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nice explanation. You made it look so simple. Thanks.

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      damn I only knew binary search

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Amazing idea!!!

    • »
      »
      »
      45 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks a lot

  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What exactly D asks for?

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Given a directed graph, find paths such that there are K vertices in it. Choose a path such that the maximum value of the vertex is the minimum possible. Output this value.

  • »
    »
    2 days ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    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.

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the approach for problem A ?

  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
2 days ago, # |
  Vote: I like it -8 Vote: I do not like it

E was nice construction problem, I like it.

But whole contest was spoiled by unclear problem statements, except A there was not a single one I clearly understood. Had to decipher and guess the meaning of all texts, annoying.

»
2 days ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

me about to solve A in 6 mins.

1st error (Not considering the edge case of n == 2) be like: "I will make you pay"

2nd error (forgetting to return after printing -1) be like: "LMAO NOOB"

And that's how 'A' ruined my LIFE :)

»
2 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone tell me why do i get TL in B

https://codeforces.com/contest/1679/submission/157177370 ?

  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      It is just a multiplication of two integers.

      • »
        »
        »
        »
        2 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Sorry for the previous nonsense reply, I just read too fast and thought you were creating a list. I got your code accepted by reading the whole input at the start.

        • »
          »
          »
          »
          »
          2 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Great. Is it fine though, that such optimizations are needed for code to be accepted. Or it is a problem of a contest?

          • »
            »
            »
            »
            »
            »
            2 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I agree this should not be needed. But I had a look at some of the accepted Python solutions and it seems they write at the start input = sys.stdin.readline which I guess is way faster. Using that your code also gets accepted, so you should write that and keep reading input as you did, which is not a big deal.

  • »
    »
    2 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for the early end round,that i could see RNG's exciting game:(

»
2 days ago, # |
  Vote: I like it +12 Vote: I do not like it

This was a super cool round with nice algorithmic problems ! Congrats to the authors :D

Here is my advice about each problem

A
B
C
D

I didn't solve E/F so I don't really have an advice but they both look interesting

  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how to solve d?

    • »
      »
      »
      47 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Problems asking to minimize the maximum (or maximize the minimum) can be solved with binary search in 99% of the cases because fixing the max/min gives you a smaller structure where you have complete freedom (for example in this problem, you don't have to care anymore about whether you move on a too big node)

      So let's binary search over the maximum node you will walk on (I don't explain why you can binary search here but you can try to prove it as an exercise)

      Now we need to check if it's possible to find a path of length k (in terms of nodes) using only nodes with value <= MX

      Let's build a new graph. It'll be the same graph as the original one but only with nodes having value <= MX. We now want to find a path of length at least k. Notice that if the graph has a cycle, we can just keep moving in the cycle and get a path of length at least k. If the graph doesn't have any cycle, it's a directed acyclic graph and you can use dp to compute the longest path in it.

      Code: 157170838

»
2 days ago, # |
  Vote: I like it +11 Vote: I do not like it

Since I am poor in English, can anyone explain what is the difference between loops and cycles? Why "loop" is equal to "self-loop" instead of "cycle" in D?

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain a solution for Problem B? (without using segment trees)

  • »
    »
    2 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Yes! You can read about it right here

  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hint: keep timestamp of modifing for each item

  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Notice that if operation of type 2 is never carried out, then the sum would only change by x — arr[i]. Also set arr[i] = x.

    If the operation of type 2 is carried out, sum for that round will be n*x. Set a boolean flag for all subsequent operations of type 1 will change.

    After even a single operation of type 2, maintain a map that tracks the most recent entry value of the indices. Note that we don't need to track the unmodified indices, as they will be x only (where x represents most recent value of type 2 operation)

    Lastly on every occurrence of type 2 operation, make sure that this map is cleared out.

  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Someone really wrote seg tree there?)

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Me who can't be bothered to think of a linear solution... I'm a simple man, I find any passable solution, I type it up

  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The contest was very nice but the pretest cases for problem C were not strong enough and any simple brute-force (TLE) solution will pass it. Let's imagine there is a cheater who created a fake account and joined the contest and then he wrote a simple brute-force solution for it and then he lock his solution and read the solutions of others to submit it from his real account.

»
2 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can someone please explain why I am getting TLE in C? https://codeforces.com/contest/1679/submission/157197783 I am using hashing to figure out when to add/delete row/column in sortedset(made using Fenwick Tree). And to find out if the whole sub-rectangle is there, I just subtract indexes with lower_bounds of x1,x2 in row sortedset and y1,y2 in column sortedset and compare it with difference of x1,x2 and y1,y2. It should be O(nlogn) but sadly it's giving TLE:(

»
2 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Testcase 41 is on fire

»
2 days ago, # |
  Vote: I like it +1 Vote: I do not like it

so many fst on problem C and D..

»
2 days ago, # |
  Vote: I like it +4 Vote: I do not like it

Several stupid mistakes on A and D led to the terrible penality and the rapid descent of rank.

»
2 days ago, # |
  Vote: I like it +6 Vote: I do not like it
  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I really don't know what these cheaters will gain from this sh!t. I think it will be better to ban any cheater forever.

    here is an example

»
2 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Sad to get FST on E :(

(my solution isn't the best solution so it got TLE on test 10.)

»
2 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E

Can any one explain why in input

2 ?? 1 ab

10 palindrome substring

(a, b, aa, bb, a, b which other?)

»
2 days ago, # |
  Vote: I like it +87 Vote: I do not like it

To not keep you waiting, the ratings are updated preliminarily. In a few days, I will remove cheaters and update the ratings again!

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me what's wrong with my code for Problem C. I was expecting a TLE but got a WA on the 27284th token!

It's in Go, but easy to understand. Uses 2 bool arrays for x and y and just loops over x1->x2 && y1->y2.

https://codeforces.com/contest/1679/submission/157188079

  • »
    »
    2 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    If I add two rooks on same row and then remove one of them, in that case your code is considering that there is no rook on that row. Because of this

    mx[x] = false
    my[y] = false
    

    You should store frequency of rooks on particular row and col to resolve this

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, I feel so dumb. These start times are killer for NA users.

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell what's wrong with my submission? Passed the pretests but failed on Test 10. https://codeforces.com/contest/1679/submission/157152675

»
2 days ago, # |
  Vote: I like it +1 Vote: I do not like it

write x<n instead of x<=n in the Fenwick tree and got fst on C. What a pity!

»
2 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can anyone tell me what's wrong with my submission? Passed the pretests but failed Test 22.

My Code...

»
2 days ago, # |
  Vote: I like it +14 Vote: I do not like it

Problem b guarantees 1≤ai≤109 but why 0 appears in test6

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

where can i get the editorial of this contest??

»
2 days ago, # |
  Vote: I like it +5 Vote: I do not like it

Can anyone tell me why I got runtime error? my submissions

  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    template <typename T>
    struct Fenwick {
        const int n;
        std::vector<T> a;
        Fenwick(int n) : n(n), a(n) {}
        void add(int x, T v) {
            for (int i = x; i <= n; i += i & -i) {
                a[i] += v;
            }
        }
        T sum(int x) {
        	if(x <= 0)return 0;
            T ans = 0;
            for (int i = x; i > 0; i -= i & -i) {
                ans += a[i];
            }
            return ans;
        }
        T rangeSum(int l, int r) {
            return sum(r) - sum(l);
        }
    };
    

    your code get an out of bound error when i == n (a[n] will out of bound).

    you should let your vector resize to n + 1.

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but I declare the structure Fenwick x(n + 1), y(n + 1) way.

      • »
        »
        »
        »
        2 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        In your Fenwick n = n + 1 at the same time.

        for (int i = x; i <= n; i += i & -i) {
            a[i] += v;
        }
        

        In this for loop, the n is 1 larger than the n your input. So a[n] will out of bound even if you declare the structure Fenwick x(n + 1000), y(n + 1000).

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ok, got it, Thank you

    • »
      »
      »
      34 hours ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      i also got runtime, when i initialize with n+1 i get RE when initialize with n+2 it passes and when i initialize with n+3 it again gives RE. i couldnt understand why edit: it gets accepted in c++20

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please find a test case where this code (157177615) fails. I have tried to come up with a failing test case but have had no success.

»
2 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Why the system is testing again ?

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What happened, why is task B being retested?

»
2 days ago, # |
  Vote: I like it +10 Vote: I do not like it

Thx the contest.Become Master at last!

»
2 days ago, # |
  Vote: I like it +1 Vote: I do not like it

who else had a rounding error in problem A haha

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the Problems . It was a pretty balanced round

»
2 days ago, # |
  Vote: I like it -19 Vote: I do not like it

我小号第一次进前一千!!!

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone see my solution for C I find nothing time consuming here. Can any minor changes make it acceptable.

  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Aren't you iterating over rows and columns for each query though?

  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I mean you have those two loops in your code:

    for i in range (q):
      for i in range (a[1], a[3]+1):
    
    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you! Can you also please suggest other efficient ways to do it with same logic(like checking if all any one of columns or rows are filled) if possible. Or is there any other logic for this

      • »
        »
        »
        »
        2 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        fenwick tree or segment tree to check sum or minimum in the range.

      • »
        »
        »
        »
        2 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I've done this problem the same way as you (logic wise). You can look at my submission.

        However, I used C++'s set and its 'lower_bound' function. I guess you can find something similar in python :)

        Maybe there is even some simpler way to solve it but I can't think of anything.

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I am getting WA on test 2 but I can not find what is mistake. Please someone check it . https://codeforces.com/contest/1679/my

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone tell me how to solve D plz

  • »
    »
    2 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Binary search the answer, then you need to judge if there is a cycle or a path with a length of at least k containing vertices with number <= answer. You can do toposort or dfs. My submission

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm screwed!

How to be better ?

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Imao the limit on C has been too tight. Whether solution is accepted or not is up to constants and the judging machine. These two submits differ only in a tab (begining of main), however only one gets ACC: 157217055 157214568

(Played with it after the round so there might be some diffrence but the point remains anyway.)

  • »
    »
    2 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    you are returning a string level by level in segment tree, which could be much slower. Change it to an enum and it will finish in ~300ms.

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help me figure out what went wrong with my solution on problem C?

What i was doing is: - store how many free rows/cols we have upto a certain row lets say r and c (using 2 BITs)

  • when u place a rook at row r and col c, u reduce the number of free rows and cols at row r and c
  • when u remove a rook u add 1 free row/col
  • to check if all rows and cols in a certain range are under attack by a rook simply check if there are 0 free rows or columns in that range
  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You need to consider the case where two rokes are in one row. After removing one of them the other one is still on that row.

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Got it thanks, realised the flaw in my approach now

  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to check if all rows and column in that submatrix is attacking by rook in log(n) time,beacuse it will take o(n) time

    • »
      »
      »
      38 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can keep track of how many free rows and cols are there in a certain range using BIT or Segment Tree (search operation logN). To handle the edge case of rook being placed in same row/col multiple times, I used a map to store number of rooks in a row and col. Then I only update the BIT when there are either 0 rooks in a row/col (means the row is free) or 1 rook (any more than this won't make the row unoccupied so only update it once).

      Here's my submission

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for problem B, it was tougher than regular div 2 B problems ( according to me ), took me 30mins to think.

THANKS A LOT

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

public class C {

public static void main(String[] args)
{
    FastReader sc = new FastReader();  
    int t = 1;
    while(t-- >0)
    {
        int n = sc.nextInt();
        int q = sc.nextInt();
        boolean rows[] = new boolean[n];
        boolean cols[] = new boolean[n];

        outer:while(q-->0)
        {
           int type = sc.nextInt();
           if(type==1)
           {
             int x = sc.nextInt()-1;
             int y = sc.nextInt()-1;
             rows[x] = true;
             cols[y] = true;
           }
           else if(type==2)
           {
             int x = sc.nextInt()-1;
             int y = sc.nextInt()-1;
             rows[x] = false;
             cols[y] = false;
           }
           else
           {
             int x1 = sc.nextInt()-1;
             int y1 = sc.nextInt()-1;
             int x2 = sc.nextInt()-1;
             int y2 = sc.nextInt()-1;

             boolean done = true;
             for(int i=x1;i<=x2;i++)
             {
              if(!rows[i])
              {
                  done = false;
                  break;
              }
             }
             if(done)
             {
              System.out.println("Yes");
              continue outer;
             }
             done = true;
             for(int j=y1;j<=y2;j++)
          {
              if(!cols[j])
              {
                 done = false;
                 break;
              }
          }
             if(done)
             {
              System.out.println("Yes");
              continue outer;
             }
             System.out.println("No");
           }
        }

    }
}

// Can anyone help me figure out the test case, where this solution would fail?

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why my solution of Problem C is giving WA on Test Case 3?

  • »
    »
    2 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    And even if it passed test case 3 it will get TLE for sure! Your solution is O(n^2) and the constraint is 2*10^5 Make sure to learn the Fenwick tree first to solve this problem

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It can be solved with c++ set

      • »
        »
        »
        »
        2 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Please explain this solution in c++ set.

        • »
          »
          »
          »
          »
          2 days ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          For rows:

          store in set every value that is not covered by any rook.

          initially this set is obv full.

          to know whether there exists a row between x1 and x2 that is not covered you make use of set.lower_bound()

          if lower_bound(x1) is set.end() or its value is > x2 then all cells between x1 and x2 must be covered

          same for columns

          • »
            »
            »
            »
            »
            »
            2 days ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            Nice Idea Thanks a lot. They should put this in the Tutorial Beside the Fenwick tree.

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      perhaps it can be solved using ordered set.

»
2 days ago, # |
  Vote: I like it +3 Vote: I do not like it

For some reason I couldn't come up with using segment tree for C, instead I used a complicated data structure that contains every consecutive segments. I believe it is useful for some specific problems, but it was an overkill for this problem. It is implemented with a set<pair<int, int>> where each pair represents the endpoints of each segment. Each operation is implemented in these ways:

  • To insert a new element x, check if there is a segment that contains x-1 and x+1, respectively. If a segment [l, x-1] exists, remove it and insert [l, x]. If a segment [x+1, r] exists, remove it and insert [x, r]. If both exist, remove both and insert [l, r]. If none of them exist, just insert [x, x]
  • To remove an element x, search for a segment [l, r] that contains x. Remove this segment, and insert [l, x-1] and [x+1, r], if l != x and x != r, respectively.

Every operation can be done in $$$\mathcal{O}(\log{n})$$$ time. Searching for segments around x can be done with set::lower_bound or set::upper_bound and decrementing the iterator if needed.

AC code: 157170732

  • »
    »
    47 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Forgot to mention the part that checks the answer. For a query [x1, x2], we just need to find a segment that includes x1, and see if that segment also includes x2.

  • »
    »
    44 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Looks like a weakened version of Chtholly Tree (or to use a more accurate description, maintenance of connected color segments).

»
47 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone suggest similar problem like D

»
47 hours ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Problem A 157243966 Can anyone check is this solution is correct or not because in verdict it is showing In Queue.

»
46 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

great job never mind but u need better choice win better an do better code is life and a way to win so i will help if need job or help so win

»
34 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
33 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain why my solution from problem C is giving TLE. 157292933

Thanks

»
33 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

My video editorial: https://youtu.be/Qa9gabukKqg