fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define MD (1000000007U)
  5. void*wmem;
  6. char memarr[96000000];
  7. template<class S, class T> inline S min_L(S a,T b){
  8.   return a<=b?a:b;
  9. }
  10. template<class S, class T> inline S max_L(S a,T b){
  11.   return a>=b?a:b;
  12. }
  13. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  14.   static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  15.   (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  16.   (*arr)=(T*)(*mem);
  17.   (*mem)=((*arr)+x);
  18. }
  19. template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
  20.   walloc1d(arr, x2-x1, mem);
  21.   (*arr) -= x1;
  22. }
  23. struct Modint{
  24.   unsigned val;
  25.   Modint(){
  26.     val=0;
  27.   }
  28.   Modint(int a){
  29.     val = ord(a);
  30.   }
  31.   Modint(unsigned a){
  32.     val = ord(a);
  33.   }
  34.   Modint(long long a){
  35.     val = ord(a);
  36.   }
  37.   Modint(unsigned long long a){
  38.     val = ord(a);
  39.   }
  40.   inline unsigned ord(unsigned a){
  41.     return a%MD;
  42.   }
  43.   inline unsigned ord(int a){
  44.     a %= (int)MD;
  45.     if(a < 0){
  46.       a += MD;
  47.     }
  48.     return a;
  49.   }
  50.   inline unsigned ord(unsigned long long a){
  51.     return a%MD;
  52.   }
  53.   inline unsigned ord(long long a){
  54.     a %= (int)MD;
  55.     if(a < 0){
  56.       a += MD;
  57.     }
  58.     return a;
  59.   }
  60.   inline unsigned get(){
  61.     return val;
  62.   }
  63.   inline Modint &operator+=(Modint a){
  64.     val += a.val;
  65.     if(val >= MD){
  66.       val -= MD;
  67.     }
  68.     return *this;
  69.   }
  70.   inline Modint &operator-=(Modint a){
  71.     if(val < a.val){
  72.       val = val + MD - a.val;
  73.     }
  74.     else{
  75.       val -= a.val;
  76.     }
  77.     return *this;
  78.   }
  79.   inline Modint &operator*=(Modint a){
  80.     val = ((unsigned long long)val*a.val)%MD;
  81.     return *this;
  82.   }
  83.   inline Modint &operator/=(Modint a){
  84.     return *this *= a.inverse();
  85.   }
  86.   inline Modint operator+(Modint a){
  87.     return Modint(*this)+=a;
  88.   }
  89.   inline Modint operator-(Modint a){
  90.     return Modint(*this)-=a;
  91.   }
  92.   inline Modint operator*(Modint a){
  93.     return Modint(*this)*=a;
  94.   }
  95.   inline Modint operator/(Modint a){
  96.     return Modint(*this)/=a;
  97.   }
  98.   inline Modint operator+(int a){
  99.     return Modint(*this)+=Modint(a);
  100.   }
  101.   inline Modint operator-(int a){
  102.     return Modint(*this)-=Modint(a);
  103.   }
  104.   inline Modint operator*(int a){
  105.     return Modint(*this)*=Modint(a);
  106.   }
  107.   inline Modint operator/(int a){
  108.     return Modint(*this)/=Modint(a);
  109.   }
  110.   inline Modint operator+(long long a){
  111.     return Modint(*this)+=Modint(a);
  112.   }
  113.   inline Modint operator-(long long a){
  114.     return Modint(*this)-=Modint(a);
  115.   }
  116.   inline Modint operator*(long long a){
  117.     return Modint(*this)*=Modint(a);
  118.   }
  119.   inline Modint operator/(long long a){
  120.     return Modint(*this)/=Modint(a);
  121.   }
  122.   inline Modint operator-(void){
  123.     Modint res;
  124.     if(val){
  125.       res.val=MD-val;
  126.     }
  127.     else{
  128.       res.val=0;
  129.     }
  130.     return res;
  131.   }
  132.   inline operator bool(void){
  133.     return val!=0;
  134.   }
  135.   inline operator int(void){
  136.     return get();
  137.   }
  138.   inline operator long long(void){
  139.     return get();
  140.   }
  141.   inline Modint inverse(){
  142.     int a = val;
  143.     int b = MD;
  144.     int u = 1;
  145.     int v = 0;
  146.     int t;
  147.     Modint res;
  148.     while(b){
  149.       t = a / b;
  150.       a -= t * b;
  151.       swap(a, b);
  152.       u -= t * v;
  153.       swap(u, v);
  154.     }
  155.     if(u < 0){
  156.       u += MD;
  157.     }
  158.     res.val = u;
  159.     return res;
  160.   }
  161.   inline Modint pw(unsigned long long b){
  162.     Modint a(*this);
  163.     Modint res;
  164.     res.val = 1;
  165.     while(b){
  166.       if(b&1){
  167.         res *= a;
  168.       }
  169.       b >>= 1;
  170.       a *= a;
  171.     }
  172.     return res;
  173.   }
  174.   inline bool operator==(int a){
  175.     return ord(a)==val;
  176.   }
  177.   inline bool operator!=(int a){
  178.     return ord(a)!=val;
  179.   }
  180. }
  181. ;
  182. inline Modint operator+(int a, Modint b){
  183.   return Modint(a)+=b;
  184. }
  185. inline Modint operator-(int a, Modint b){
  186.   return Modint(a)-=b;
  187. }
  188. inline Modint operator*(int a, Modint b){
  189.   return Modint(a)*=b;
  190. }
  191. inline Modint operator/(int a, Modint b){
  192.   return Modint(a)/=b;
  193. }
  194. inline Modint operator+(long long a, Modint b){
  195.   return Modint(a)+=b;
  196. }
  197. inline Modint operator-(long long a, Modint b){
  198.   return Modint(a)-=b;
  199. }
  200. inline Modint operator*(long long a, Modint b){
  201.   return Modint(a)*=b;
  202. }
  203. inline Modint operator/(long long a, Modint b){
  204.   return Modint(a)/=b;
  205. }
  206. template<class T> struct fenwick{
  207.   int size;
  208.   int memory;
  209.   T*data;
  210.   void malloc(int mem);
  211.   void malloc(int mem, int fg);
  212.   void walloc(int mem, void **workMemory = &wmem);
  213.   void walloc(int mem, int fg, void **workMemory = &wmem);
  214.   void free(void);
  215.   void init(int N);
  216.   void add(int k, T val);
  217.   T get(int k);
  218.   T range(int a, int b);
  219.   int kth(T k);
  220. }
  221. ;
  222. #define main dummy_main
  223. int main(){
  224.   wmem = memarr;
  225.   return 0;
  226. }
  227. #undef main
  228. class Solution{
  229.   public:
  230.   int createSortedArray(vector<int>& A){
  231.     int i;
  232.     dummy_main();
  233.     int N = A.size();
  234.     int Lj4PdHRW;
  235.     int KL2GvlyY;
  236.     if(N==0){
  237.       KL2GvlyY = 0;
  238.     }
  239.     else{
  240.       KL2GvlyY = A[0];
  241.       for(Lj4PdHRW=(1);Lj4PdHRW<(N);Lj4PdHRW++){
  242.         KL2GvlyY = max_L(KL2GvlyY, A[Lj4PdHRW]);
  243.       }
  244.     }
  245.     int mx = KL2GvlyY+ 1;
  246.     Modint res = 0;
  247.     fenwick<int> t;
  248.     t.walloc(mx+1,1);
  249.     for(i=(0);i<(N);i++){
  250.       t.add(A[i], 1);
  251.       res +=min_L(t.get(A[i]-1), t.range(A[i]+1,mx));
  252.     }
  253.     return res;
  254.   }
  255. }
  256. ;
  257. template<class T> void fenwick<T>::malloc(int mem){
  258.   memory = mem;
  259.   data = (T*)std::malloc(sizeof(T)*mem);
  260. }
  261. template<class T> void fenwick<T>::malloc(int mem, int fg){
  262.   memory = mem;
  263.   data = (T*)std::malloc(sizeof(T)*mem);
  264.   if(fg){
  265.     init(mem);
  266.   }
  267. }
  268. template<class T> void fenwick<T>::walloc(int mem, void **workMemory /* = &wmem*/){
  269.   memory = mem;
  270.   walloc1d(&data, mem, workMemory);
  271. }
  272. template<class T> void fenwick<T>::walloc(int mem, int fg, void **workMemory /* = &wmem*/){
  273.   memory = mem;
  274.   walloc1d(&data, mem, workMemory);
  275.   if(fg){
  276.     init(mem);
  277.   }
  278. }
  279. template<class T> void fenwick<T>::free(void){
  280.   memory = 0;
  281.   free(data);
  282. }
  283. template<class T> void fenwick<T>::init(int N){
  284.   size = N;
  285.   memset(data,0,sizeof(T)*N);
  286. }
  287. template<class T> void fenwick<T>::add(int k, T val){
  288.   while(k < size){
  289.     data[k] += val;
  290.     k |= k+1;
  291.   }
  292. }
  293. template<class T> T fenwick<T>::get(int k){
  294.   T res = 0;
  295.   while(k>=0){
  296.     res += data[k];
  297.     k = (k&(k+1))-1;
  298.   }
  299.   return res;
  300. }
  301. template<class T> T fenwick<T>::range(int a, int b){
  302.   if(b==-1){
  303.     b=size-1;
  304.   }
  305.   return get(b) - get(a-1);
  306. }
  307. template<class T> int fenwick<T>::kth(T k){
  308.   int i=0;
  309.   int j=size;
  310.   int c;
  311.   T v;
  312.   while(i<j){
  313.     c = (i+j)/2;
  314.     v = get(c);
  315.     if(v <= k){
  316.       i=c+1;
  317.     }
  318.     else{
  319.       j=c;
  320.     }
  321.   }
  322.   return i==size?-1:i;
  323. }
  324. // cLay varsion 20201102-1
  325.  
  326. // --- original code ---
  327. // #define main dummy_main
  328. // {}
  329. // #undef main
  330. // 
  331. // class Solution {
  332. // public:
  333. //   int createSortedArray(vector<int>& A) {
  334. //     dummy_main();
  335. //     int N = A.size(), mx = max(A(N)) + 1;
  336. //     Modint res = 0;
  337. //     fenwick<int> t;
  338. //     t.walloc(mx+1,1);
  339. //     rep(i,N){
  340. //       t.add(A[i], 1);
  341. //       res += min(t.get(A[i]-1), t.range(A[i]+1,mx));
  342. //     }
  343. //     return res;
  344. //   }
  345. // };
  346.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/91FdHw
language:
C++ (gcc 8.3)
created:
3 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!