fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct sg_tree
  6. {
  7.     static const int MPOW=16;
  8.     static const int n=1<<MPOW;
  9.     int arr[n];
  10.  
  11.     sg_tree(){fill(arr,arr+n,0);}
  12.  
  13.     void add(int x)
  14.     {
  15.         x+=1<<MPOW-1;
  16.         arr[x]=1;
  17.         while(x>>=1)
  18.             arr[x]=arr[x<<1]+arr[(x<<1)+1];
  19.     }
  20.     int sum(int c,int cl,int cr,int l,int r)
  21.     {
  22.         if(l>r)
  23.             return 0;
  24.         if(l==cl && r==cr)
  25.             return arr[c];
  26.         int cm=(cl+cr)>>1;
  27.         return sum(c<<1,cl,cm,l,min(cm,r))+sum((c<<1)+1,cm+1,cr,max(cm+1,l),r);
  28.     }
  29.     int get(int x)
  30.     {
  31.         return sum(1,0,(1<<MPOW-1)-1,0,x);
  32.     }
  33. };
  34.  
  35. main()
  36.  {
  37.     ios::sync_with_stdio(0);
  38.     cin.tie(0);
  39.     int n,k;
  40.     cin>>n>>k;
  41.     int maxi=0,ans=1;
  42.     for(int i=0;i<k;i++)
  43.     {
  44.         sg_tree army;
  45.         int cur=0,h;
  46.         for(int j=0;j<n;j++)
  47.         {
  48.             cin>>h;
  49.             cur+=j-army.get(h);
  50.             army.add(h);
  51.         }
  52.         if(cur>maxi)
  53.             maxi=cur,ans=i+1;
  54.     }
  55.     cout<<ans<<endl;
  56. }
  57.  
Success #stdin #stdout 0s 3620KB
comments (?)
stdin
copy 
3 3
1 2 3
2 1 3
3 2 1
stdout
copy 
3
https://ideone.com/iI2d9A
language:
C++14 (gcc 8.3)
created:
10 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!