SHOW:
|
|
- or go back to the newest paste.
1 | n, s = gets.strip.split(' ') | |
2 | n = n.to_i | |
3 | s = s.to_i | |
4 | ||
5 | used_start_poins = Hash.new | |
6 | used_end_points = Hash.new | |
7 | ||
8 | for a0 in (0..s-1) | |
9 | l, r = gets.strip.split(' ') | |
10 | l = l.to_i | |
11 | r = r.to_i | |
12 | ||
13 | sum = 0 | |
14 | if l > 0 | |
15 | sum += r*(r+1)/2 - (l*(l-1)/2) | |
16 | else | |
17 | sum += r*(r+1)/2 | |
18 | end | |
19 | ||
20 | used_start_poins[l]=r | |
21 | used_end_points[r]=l | |
22 | ||
23 | left = l-1 | |
24 | ||
25 | while left > 0 | |
26 | i = used_end_points[left] | |
27 | ||
28 | if i | |
29 | left = used_start_poins[i]-1 | |
30 | else | |
31 | sum += left | |
32 | used_start_poins[l]=l | |
33 | used_end_points[l]=l | |
34 | break | |
35 | end | |
36 | end | |
37 | ||
38 | right = r+1 | |
39 | ||
40 | while right < n | |
41 | i = used_start_poins[right] | |
42 | ||
43 | if i | |
44 | right = used_end_points[i]+1 | |
45 | else | |
46 | - | used_start_poins[r]=r |
46 | + | |
47 | used_start_poins[r]=r | |
48 | used_end_poins[r]=r |