fork download
copy 
  1. /*khanghaicode da loiihunter*/
  2. /*--------------------------*/
  3. /*Ai doc cai nay la gay*/
  4. /*Whoever reads this is gay*/
  5. /*Celui qui lit ceci est gay*/
  6. /*Wer das liest, ist schwul*/
  7. /*khong code thi thoi t la mot con cho*/
  8. /*chim trong man dem nazuna cuu lay toi*/
  9. // ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⣀⠀⣤⣤⣤⣤⣤⣤⣄⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀
  10. // ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣶⠿⠟⠉⠉⠀⠉⠁⠘⢉⣉⣛⠛⣿⠻⠷⣶⣄⡀⠀⠀⠀⢀⣴⣿⣶⣶⡾⣿⡿⠟
  11. // ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⡾⠟⠋⠁⠀⡄⠀⠀⠀⠀⠀⢰⠈⢿⡏⠻⣿⣿⣷⣮⠉⠃⣴⣦⡾⢫⡏⠉⠉⣥⣿⣿⣶
  12. // ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⡾⠃⣀⣴⣾⣷⠋⠃⠁⠀⠀⠀⠀⠀⠀⠈⠘⠀⠁⡏⠹⣿⣦⡀⠀⢙⢿⣥⣥⠶⠟⠛⠛⠉
  13. // ⠀⠀⠐⠶⢶⣖⡒⠲⠦⠤⢤⣼⡟⢻⠷⡿⠛⠁⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⠀⠀⢠⠈⢯⠻⣄⢠⠆⣿⣹⡷⢦⡄
  14. // ⠀⢀⣨⣿⠋⢉⣀⣀⣠⣤⣶⡟⣳⢋⡞⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣦⣧⡄⢀⠀⠀⠀⢨⣦⠈⣿⠘⣿⣉⣀⣠⣏
  15. // ⠾⠿⠻⠿⣿⣿⣿⡿⣿⠿⢹⣿⢏⣿⠁⠀⠀⠀⢠⠀⣀⣴⡟⠀⠀⠀⠀⠀⠀⡏⠃⠻⠾⠀⠀⠸⢹⠀⠘⣷⣿⣻⡟⢿⠛⢷
  16. // ⠀⠀⠀⠀⠉⠁⠀⣠⣿⣷⣿⡟⢸⡇⠀⠀⡀⣀⣼⢾⠛⡇⣷⢰⢰⢸⢸⡆⢸⠇⢠⣀⠀⢀⡀⠀⣬⠀⠀⡸⣿⡿⢷⣶⣤⣼
  17. // ⠀⠀⠀⠀⠀⠀⢀⣿⣦⢠⣿⠁⣿⠀⡄⣼⣿⡍⢿⣄⠆⠃⠋⠈⠈⠈⠀⠁⢠⣄⣾⣭⣤⣬⣥⣼⡏⠀⠀⡇⣿⡇⣿⣅⠸⠇⣇
  18. // ⠀⠀⠀⠀⠀⢠⡞⠉⢹⣸⠇⠀⣿⡄⣇⢻⣿⡳⢈⣸⣶⣖⣆⠀⠀⠀⠀⠀⠈⠚⠉⠉⠉⠙⢻⣿⡷⠀⠀⠀⢻⣷⢈⡿⠦⣤⡟
  19. // ⠀⠀⠀⠀⠀⢈⣿⣤⣤⡿⠀⠀⠙⢻⣟⠛⣥⣾⠟⠋⠁⠀⠀⠀⠀⡖⠀⠀⠀⠀⠀⠀⠂⣿⡾⠁⠀⣀⠀⠀⢸⣿⠸⣧⠐⠁⢸
  20. // ⠀⠀⠀⠀⠀⣿⡀⠙⣿⡇⠀⠀⠀⠸⣿⣷⠛⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣼⠟⠁⣀⡤⡿⠀⠀⣼⠻⠏⠉⡃⠴⣇
  21. // ⠀⠀⠀⠀⠀⣽⠿⣿⣿⠁⢀⣤⡄⠀⢻⣿⣶⡏⠀ ⠀⠀⢀⣀⣤⣤⣶⠶⠿⣛⣿⣟⣯⣶⣿⣿⣿⠃⠀⣰⡿⢛⡷⠀⠃⢀⣿
  22. // ⠀⠀⠀⠀⠀⢿⣶⣼⣿⢀⣾⣧⠀⠀⡰⣿⣿⡁⠀⠀⠀⣼⣿⣿⠏⠁⠀⠀⠀⠙⠉⠉⠉⣹⣿⢟⡟⢠⡾⢫⣴⡿⣷⣦⣴⠏⠁
  23. // ⠀⠀⠀⠀⢰⣟⣀⣻⣿⣿⣷⣿⣦⣠⣿⣿⡽⣿⣄⠀⠀⢹⣿⡃⠀⠀⠀⠀⠀⠀⠀⣀⣴⣯⣀⣾⣷⡟⣱⣟⣼⣷⣶⡸⢿⣀⣠⣤⣴⣶
  24. // ⠀⠀⠀⠀⠈⣿⠛⢻⣿⣿⠽⠿⠈⣻⡟⣿⣿⣿⡻⣿⣤⣀⠙⠿⣤⣤⡄⠀⠀⠤⠘⠙⣿⣿⣿⣿⠟⢠⣿⠟⢁⣠⣯⣿⣿⣿⣿⣿⣿⣿
  25. // ⠀⠀⠀⠀⠀⠻⣶⠾⣿⡟⣸⣏⠛⢯⣄⣸⣄⣼⡧⠛⢿⡿⠙⢶⣤⣀⠀⠀⠀⢀⣠⣾⡿⠉⡾⢿⡴⠋⢀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  26. // ⠀⠀⠀⠀⠀⠀⢻⣆⣨⡿⣃⣩⣿⣦⣌⡉⠻⢏⠁⠀⠀⣻⠀⠸⣿⣿⣿⣷⡾⠛⣿⠋⠀⠀⠀⠈⠇⣴⠉⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  27. // ⠀⠀⠀⠀⠀⠀⠀⣻⣿⣿⣿⣿⣿⣿⣿⣿⣦⣼⠇⢷⣄⠇⡄⠀⣿⣿⣿⣿⡇⠞⠀⡄⠀⠾⠆⠀⠀⣿⣠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  28. // ⠀⠀⠀⠀⠀⢠⣶⣿⣿⣿⡿⠿⠻⣿⣽⣷⣿⣆⠀⠀⠙⠷⣅⠀⢿⣿⣿⣿⡅⠀⠀⡟⡜⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  29. // ⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣷⣾⣿⣿⣿⣿⣿⣿⡆⠀⠀⠀⠹⠀⠸⣿⣿⣿⣷⡀⠸⢰⠁⠀⢰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  30. // ⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⡀⠀⠀⠀⠀⢰⣿⣿⣿⣿⡟⠇⠈⠀⠀⢸⣿⣿⣿⡿⠛⠉⠉⠙⠻⣿⣿⣿⣿⣿⣿
  31. // ⠀⠀⠀⠀⠀⠈⢻⣿⣿⡟⣿⣯⣼⠟⠋⠻⢿⣿⣿⣇⠀⠀⠀⡰⢠⣿⣿⣿⣿⣿⠀⢳⣀⣀⢿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⠙⣿⣿⣿⣿
  32. #include <bits/stdc++.h>
  33. using namespace std;
  34. int n,m;
  35. vector<int>g[100001];
  36. int a[100001];
  37. int sus[100001];
  38. vector<int>ds[100001];
  39. vector<int>nen;
  40. int cnt[100001];
  41. int findsus(int x){
  42.     if(!sus[x])return x;
  43.     return sus[x]=findsus(sus[x]);
  44. }
  45. void unionsus(int x,int y){
  46.     x=findsus(x);
  47.     y=findsus(y);
  48.     if(x==y)return;
  49.     sus[y]=x;
  50.     cnt[x]+=cnt[y];
  51.     cnt[y]=0;
  52. }
  53. bool dd[100001];
  54. void process(){
  55.     long long ans=0;
  56.     for(int val=1;val<=n;val++){
  57.         for(int u:ds[val]){
  58.             cnt[u]++;
  59.             for(int v:g[u]){
  60.                 if(a[v]<=val)unionsus(u,v);
  61.             }
  62.         }
  63.         for(int &u:ds[val]){
  64.             u=findsus(u);
  65.             if(dd[u])continue;
  66.             dd[u]=1;
  67.             ans+=(long long)cnt[u]*(cnt[u]-1)/2;
  68.             cnt[u]=0;
  69.         }
  70.         for(int u:ds[val])dd[u]=0;
  71.     }
  72.     cout<<ans+n;
  73. }
  74. void init(){
  75.     cin>>n>>m;
  76.     for(int i=1;i<=n;i++){
  77.         cin>>a[i];
  78.         nen.push_back(a[i]);
  79.     }
  80.     sort(nen.begin(),nen.end());
  81.     for(int i=1;i<=n;i++){
  82.         a[i]=lower_bound(nen.begin(),nen.end(),a[i])-nen.begin()+1;
  83.         ds[a[i]].push_back(i);
  84.     }
  85.     for(int u,v,i=0;i<m;i++){
  86.         cin>>u>>v;
  87.         g[u].push_back(v);
  88.         g[v].push_back(u);
  89.     }
  90. }
  91. int main(){
  92.     ios_base::sync_with_stdio(0);cin.tie(0);
  93.     #define NAME "poibeu"
  94.     if(fopen(NAME".inp","r")){
  95.         freopen(NAME".inp","r",stdin);
  96.         freopen(NAME".out","w",stdout);
  97.     }
  98.     //clock_t begin=clock();
  99.     init();
  100.     process();
  101.     //cerr<<"\n"<<(float)(clock()-begin)/CLOCKS_PER_SEC<<"s";
  102. }
  103.  
Success #stdin #stdout 0.01s 9144KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RD1sxi
language:
C++ (gcc 8.3)
created:
7 days 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!