fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5.  
  6. int n,k;
  7.  
  8. vector<int> par;
  9. vector<int> treesize;
  10.  
  11. vector<int> luu;
  12.  
  13.  
  14. int findd(int a)
  15. {
  16.     if(a == par[a]) return a;
  17.     return par[a] = findd(par[a]);
  18. }
  19.  
  20. void unionn(int a, int b)
  21. {
  22.     a = findd(a);
  23.     b = findd(b);
  24.     par[a] = b;
  25.     treesize[b] += treesize[a];
  26. }
  27.  
  28.  
  29. void nhap()
  30. {
  31.     cin >> n >> k; n++;
  32.     par.resize(n,0);
  33.     treesize.resize(n,1);
  34.     for(int i = 0; i<n; i++) par[i] = i;
  35.  
  36. }
  37.  
  38. void process()
  39. {
  40.     luu.resize(n);
  41.     for(int i = 0; i<n; i++) luu[i] = i;
  42.     int l = 0; int r = n-1;
  43.     while(k--){
  44.         int val; cin >> val;
  45.         if(val!= par[val]) val = findd(val);
  46.         int pos = lower_bound(luu.begin() + l, luu.begin() + r + 1, val) - (luu.begin() + l);
  47.         if(pos <= (r - l) /2){
  48.             pos = l + pos;
  49.             for(int i = 1; pos - i >=l; i++) unionn(pos-i, pos+i);
  50.             l = pos;
  51.         }else{
  52.             pos = l + pos;
  53.             for(int i = 1; pos + i <=r; i++) unionn(pos +i, pos - i);
  54.             r = pos;
  55.         }
  56.     }
  57.     cout << (r - l + 1) << endl;
  58.     for(int i = l; i<=r; i++) cout << treesize[i] << ' ';
  59. }
  60.  
  61. int main()
  62. {
  63.     freopen("bando.inp","r",stdin);
  64.     freopen("bando.out","w",stdout);
  65.     nhap();
  66.     process();
  67.     return 0;
  68. }
  69.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/aBt5bP
language:
C++ (gcc 8.3)
created:
6 hours 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!