# | User | Rating |
---|---|---|

1 | tourist | 3778 |

2 | Benq | 3592 |

3 | ecnerwala | 3521 |

4 | Um_nik | 3423 |

5 | jiangly | 3375 |

6 | Petr | 3342 |

7 | Radewoosh | 3337 |

8 | scott_wu | 3313 |

9 | maroonrk | 3265 |

10 | yosupo | 3259 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 201 |

2 | 1-gon | 200 |

3 | rng_58 | 194 |

4 | SecondThread | 193 |

5 | awoo | 185 |

6 | vovuh | 183 |

7 | Um_nik | 182 |

8 | antontrygubO_o | 177 |

9 | Ashishgup | 175 |

10 | -is-this-fft- | 171 |

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/25/2021 12:42:53 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

the content isn't working now: while opening file this message is found "the archive is either in unknown format or damaged"

Very strange. Anybody has a similar problem?

Yes, me too.

I had that problem too. But when I opened that file with 7zip, it has been opened normally.

reoutloaded

Does anyone know how to solve 3rd problem (C problem) in better complexity than

O(N*sqrt(N))?Consider a set of points (

l,r) on plane such that 0 ≤l≤r≤n- 1 where the point (l,r) corresponds to a segment [l,r].Consider some number

xand all its occurrences. Suppose that the numberxis one of the numbers that make some particular segment [l,r] be bad. Then one of the following situations should happen: either there are from 1 tox- 1 or more thanx+ 1 occurrences ofxin [l,r]. That means that for the fixedlthere are two segments of banned values forr. Actually, for any possiblellying between two consectuviex's, those two banned segments forrwill be the same. It can be reformulated that there areO(c_{x}) banned rectangles on a plane that point (l,r) isn't allowed to be in, wherec_{x}is the number of occurrences ofx.Construct all such rectangles for all numbers

x, there will beO(n) of them in total, and then calculate the number of points that do not lie in any banned rectangle in via sweeping line.Although this solution has better time complexity, there are solutions that work even faster because they do not utilize much memory and use only simple operations.

Code for reference:

solution by me: http://pastebin.com/k0GHWxuQ

solution by Errichto: http://pastebin.com/UXziv4iD

Sorry, just mixed up.

Why it's ?

Isn't there supposed to be an extra line between 26 and 27 which is like line 31?

Ask not me, but Errichto.

But you are good enough to check other's code right?

nah, I'm more about writing comments :)

:)) thanks for not helping :))

.

Can someone explain the solution of problem A Day1?

The download link doesn't work for me, can you share the problem statements somewhere else?

It's in Russian anyway

Oh ok. I thought it was in english since the discussion was in english.

Problem A

GL & HF :)