fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define vi vector<int>
  5. #define fi first
  6. #define se second
  7. #define pb push_back
  8. #define ii pair<int , int>
  9. #define pq priority_queue
  10. #define iii pair<int , pair<int , int>>
  11. #define fo(i,l,r) for(int i=l;i<=r;i++)
  12. #define fod(i,r,l) for(int i=r;i>=l;i--)
  13. #define fill(f,x) memset(f,x,sizeof(f))
  14. #define NAME "file"
  15.  
  16. const int N = 2e5 + 5, mod = 1e9 + 7;
  17. int n , q;
  18. int p[N] , cnt[N] , s[N] , a[N] , tv[N] , res = 1 , ans[N];
  19. map <int , int> mp[N];
  20. bool del[N];
  21.  
  22. int socap(int n)
  23. {
  24.     return (n * (n - 1) / 2);
  25. }
  26.  
  27. int acs(int u)
  28. {
  29.     if (p[u] == u) return u;
  30.     return p[u] = acs(p[u]);
  31. }
  32.  
  33. void join(int u , int v)
  34. {
  35.     int x = acs(u);
  36.     int y = acs(v);
  37.     if (x != y)
  38.     {
  39.         if (s[x] > s[y]) swap(x , y);
  40.         p[x] = y;
  41.         s[y] += s[x];
  42.         for (auto e : mp[x])
  43.         {
  44.             cnt[y] -= socap(mp[y][e.fi]);
  45.             mp[y][e.fi] += e.se;
  46.             cnt[y] += socap(mp[y][e.fi]);
  47.         }
  48.  
  49.         res = max(res , socap(s[y]) - cnt[y] + 1);
  50.         //cout << u << ' ' << v << ' ' << y << ' ' << cnt[y] << ' ' << s[y] << ' '<< s[x]<< '\n';
  51.     }
  52. }
  53.  
  54. signed main()
  55. {
  56.     ios_base::sync_with_stdio(0);
  57.     cin.tie(0);  cout.tie(0);
  58.     //freopen(NAME".INP" , "r" , stdin);
  59.     //freopen(NAME".OUT" , "w" , stdout);
  60.  
  61.     int n , q;
  62.     cin >> n >> q;
  63.     fo(i, 1, n)
  64.     {
  65.         p[i] = i;
  66.         s[i] = 1;
  67.         cin >> a[i];
  68.         mp[i][a[i]] = 1;
  69.     }
  70.  
  71.     fo(i, 1, q)
  72.     {
  73.         cin >> tv[i];
  74.         del[tv[i]] = true;
  75.         p[tv[i]] = 0;
  76.         s[tv[i]] = 0;
  77.     }
  78.  
  79.     fo(i, 1, n - 1)
  80.     {
  81.         if (!del[i] && !del[i + 1])
  82.         join(i , i + 1);
  83.     }
  84.     ans[q] = res;
  85.  
  86.  
  87.     fod(i, q, 2)
  88.     {
  89.         int id = tv[i];
  90.         p[id] = id;
  91.         s[id] = 1;
  92.         if (id - 1 >= 1 && p[id - 1] != 0)
  93.             join(id - 1 , id);
  94.         if (id + 1 <= n && p[id + 1] != 0)
  95.             join(id , id + 1);
  96.  
  97.         ans[i - 1] = res;
  98.     }
  99.  
  100.  
  101.     fo(i, 1, q)
  102.         cout << ans[i] << '\n';
  103. }
  104. // haronnee_
Success #stdin #stdout 0.01s 12964KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
1
https://ideone.com/eEU7zW
language:
C++ (gcc 8.3)
created:
20 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!