Need help on my solution's complexity

Правка en1, от NoLongerRed, 2019-02-27 15:26:15

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.
/predownloaded/ac/ca/acca90d2b71786f9164dd08325622b77d0d54eeb.png

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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский NoLongerRed 2019-02-27 15:28:55 109
en1 Английский NoLongerRed 2019-02-27 15:26:15 1743 Initial revision (published)