fork download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5. #define maxn 100000
  6.  
  7. int n,a[maxn];
  8.  
  9. int hely(int v){// (növő sorrendben) rendezett "a" tömbben megkeresi v (egyik) pozicióját O(log(n)) időben, bináris keresés
  10.  
  11.     int p2=1,pos=0,pos2;
  12.  
  13.     while(p2<n)p2<<=1;
  14.     for(;p2;p2>>=1){
  15.         pos2=pos+p2;
  16. 	if(pos2<n&&a[pos2]<=v)pos=pos2;
  17.     }
  18.     return pos;
  19. }
  20.  
  21.  
  22. int main(void){
  23.  
  24.     int i,index,K,kulonbozo,t,b[maxn],tipus[maxn],szin[maxn],szam[maxn];
  25.     long long int ans;// az eredmény >2^32 is lehet!
  26.  
  27.     scanf("%d",&n);
  28.     for(i=0;i<n;i++){scanf("%d",&a[i]);b[i]=a[i];}
  29.  
  30.     sort(a,a+n);// állatok rendezése
  31.     K=0;
  32.     for(i=0;i<n;i++){
  33.       if(i==0||a[i]>a[i-1])K++;// új állatfaj
  34.       szin[i]=K-1;// a rendezett sorban ez a (K-1)-dik állatfaj
  35.     }
  36.     for(i=0;i<n;i++)tipus[i]=szin[hely(b[i])];// az eredeti sorrendben az i-edik állat a tipus[i]-edik állatfaj
  37.     for(i=0;i<K;i++)szam[i]=0;// szam[i] majd az i-edik álltfajt számlálja meg
  38.  
  39.     ans=0;
  40.     index=0;
  41.     kulonbozo=0;// i-edik állatig a különböző állatfajok számát "kulonbozo" adja meg
  42.     for(i=0;i<n;i++){
  43.        t=tipus[i];
  44.        if(szam[t]==0)kulonbozo++;// az i-edik új állatfaj
  45.        szam[t]++;// a t-edik állatfajból eggyel több van
  46.  
  47.        for(;kulonbozo==K;index++){// azt a legnagyobb indexet határozzuk meg, amelyre [index,i] mindegyik állatfajt tartalmazza
  48. 	                          // nyilván nagyobb i-hez nagyobb index tartozik
  49. 	                          // így ennek a ciklusnak az időgénye összesen O(n) az n értékre.
  50. 	   t=tipus[index];
  51. 	   if(szam[t]==1)break;// t-edik állatfajból 1 van, így őt nem dobhatjuk ki
  52. 	   szam[t]--;
  53.        }
  54.  
  55.        if(kulonbozo==K)ans+=index+1;// ha volt mindegyik állatfaj, akkor az i-re végződő túrák közül
  56.                                     // [j,i] pontosan akkor lesz jó, ha j<=index, ezek száma index+1
  57.     }
  58.     printf("%lld\n",ans);
  59.  
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 0s 17888KB
comments (?)
stdin
copy 
6
1 2 3 2 1 3
stdout
copy 
9
https://ideone.com/GdXUKJ
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
secret

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!