codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1250A.md (2343B)


      1 Source: https://codeforces.com/problemset/problem/1250/A
      2 
      3 A. Berstagram
      4 
      5 time limit per test
      6 
      7 3 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Polycarp recently signed up to a new social network Berstagram. He immediately published $n$ posts there. He assigned numbers from $1$ to $n$ to all posts and published them one by one. So, just after publishing Polycarp's news feed contained posts from $1$ to $n$ — the highest post had number $1$, the next one had number $2$, ..., the lowest post had number $n$.
     22 
     23 After that he wrote down all likes from his friends. Likes were coming consecutively from the $1$-st one till the $m$-th one. You are given a sequence $a_1, a_2, \dots, a_m$ ($1 \le a_j \le n$), where $a_j$ is the post that received the $j$-th like.
     24 
     25 News feed in Berstagram works in the following manner. Let's assume the $j$-th like was given to post $a_j$. If this post is not the highest (first) one then it changes its position with the one above. If $a_j$ is the highest post nothing changes.
     26 
     27 For example, if $n=3$, $m=5$ and $a=[3,2,1,3,3]$, then Polycarp's news feed had the following states:
     28 
     29 * before the first like: $[1, 2, 3]$;
     30 * after the first like: $[1, 3, 2]$;
     31 * after the second like: $[1, 2, 3]$;
     32 * after the third like: $[1, 2, 3]$;
     33 * after the fourth like: $[1, 3, 2]$;
     34 * after the fifth like: $[3, 1, 2]$.
     35 
     36 Polycarp wants to know the highest (minimum) and the lowest (maximum) positions for each post. Polycarp considers all moments of time, including the moment "before all likes".
     37 
     38 Input
     39 
     40 The first line contains two integer numbers $n$ and $m$ ($1 \le n \le 10^5$, $1 \le m \le 4 \cdot10^5$) — number of posts and number of likes.
     41 
     42 The second line contains integers $a_1, a_2, \dots, a_m$ ($1 \le a_j \le n$), where $a_j$ is the post that received the $j$-th like.
     43 
     44 Output
     45 
     46 Print $n$ pairs of integer numbers. The $i$-th line should contain the highest (minimum) and the lowest (maximum) positions of the $i$-th post. You should take into account positions at all moments of time: before all likes, after each like and after all likes. Positions are numbered from $1$ (highest) to $n$ (lowest).
     47 
     48 Examples
     49 
     50 Input
     51 
     52 ```
     53 3 5
     54 3 2 1 3 3
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 1 2
     61 2 3
     62 1 3
     63 ```
     64 
     65 Input
     66 
     67 ```
     68 10 6
     69 7 3 5 7 3 6
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 1 2
     76 2 3
     77 1 3
     78 4 7
     79 4 5
     80 6 7
     81 5 7
     82 8 8
     83 9 9
     84 10 10
     85 ```