fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class DSU {
  5. public:
  6.     DSU(int n) : _n(n) {
  7.         _fa = vector<int>(n, -1);
  8.         _sz = vector<int>(n, 0);
  9.     }
  10.     void create(int x) {
  11.         _fa[x] = x;
  12.         _sz[x] = 1;
  13.     }
  14.     int find(int x) {
  15.         if (_fa[x] == -1) return -1;
  16.         if (_fa[x] == x) return x;
  17.         return _fa[x] = find(_fa[x]);
  18.     }
  19.     bool merge(int x,int y) {
  20.         if (x == -1 || y == -1) return false;
  21.         int fx = find(x), fy = find(y);
  22.         if (fx == -1 || fy == -1) return false;
  23.         if (fx == fy) return false;
  24.         _fa[fy] = _fa[fx];
  25.         _sz[fx] += _sz[fy];
  26.         return true;
  27.     }
  28.     int get_sz(int x) {
  29.         return _sz[find(x)];
  30.     }
  31. private:
  32.     int _n;
  33.     vector<int> _fa, _sz;
  34. };
  35.  
  36. const int N=200010;
  37.  
  38. int main()
  39. {
  40.     int n;
  41.     scanf("%d",&n);
  42.     DSU dsu(N);
  43.     int pos=0;
  44.     for (int i=0;i<n;i++) {
  45.         int x;
  46.         scanf("%d",&x);
  47.         dsu.create(x);
  48.         dsu.merge(x,x-1);
  49.         dsu.merge(x,x+1);
  50.         while (dsu.find(pos) != -1) ++pos;
  51.         printf("%d\n", pos);
  52.     }
  53.     return 0;
  54. }
Success #stdin #stdout 0s 4788KB
comments (?)
stdin
copy 
10
5 4 3 2 1 0 7 7 6 6
stdout
copy 
0
0
0
0
0
6
6
6
8
8
https://ideone.com/4eoR5l
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!