UtahaSenpai's blog

By UtahaSenpai, history, 10 months ago, In English,

Recently, I tried to solve a problem on Atcoder and came up with a solution. I got accepted but have no idea of its complexity. Does anyone know its complexity and when the worst case happens?

Problem:
Given an array with N integers A1, A2, ..., AN and M intervals (L1, R1), ..., (LM, RM), you can perform the following operation arbitrary times:
Choose one of the M intervals (Li, Ri) and add ALi, ALi + 1, ..., ARi by  + 1 or  - 1.
Is it possible to make all N integers zero?
N, M ≤ 105

My solution:
First of all, if all Li are different, we can uniquely determine how many times we should perform an operation on the interval (Li, Ri) and whether we should choose  + 1 or  - 1.
Now, we try to avoid the same left bound. When we find two interval (Li, Ri), (Lj, Rj) (Ri < Rj) with the same left bound, i.e. Li = Lj, we change the second interval to (Ri + 1, Rj) (just imagine what happen if we add 1 to (Lj, Rj) and -1 to (Li, Ri)). Because each interval never change its right bound and its left bound is increasing, so we won't do this infinitely.

Here's my implementation: First, we put all right bounds of intervals that have a left bound i into a vector bound[i]. Sort all bound[i]. Starting from bound[0] to bound[100000], we do something like
bound[bound[i][j]].push_back(bound[i][j+1]);
It's basically the operation shown in the following picture.
https://drive.google.com/file/d/1q6kYHhXPCIv5N_5qHeWiG6gXrp5KjkkZ/view?usp=sharing

At first, I thought it is a O(n2) but wasn't able to construct a O(n2) test case. After coding it, I got an AC and it only runs less than 100 ms. So what's the complexity?

Read more »

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