fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. void*wmem;
  5. char memarr[96000000];
  6. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  7.   static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  8.   (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  9.   (*arr)=(T*)(*mem);
  10.   (*mem)=((*arr)+x);
  11. }
  12. inline int my_getchar_unlocked(){
  13.   static char buf[1048576];
  14.   static int s = 1048576;
  15.   static int e = 1048576;
  16.   if(s == e && e == 1048576){
  17.     e = fread_unlocked(buf, 1, 1048576, stdin);
  18.     s = 0;
  19.   }
  20.   if(s == e){
  21.     return EOF;
  22.   }
  23.   return buf[s++];
  24. }
  25. inline void rd(int &x){
  26.   int k;
  27.   int m=0;
  28.   x=0;
  29.   for(;;){
  30.     k = my_getchar_unlocked();
  31.     if(k=='-'){
  32.       m=1;
  33.       break;
  34.     }
  35.     if('0'<=k&&k<='9'){
  36.       x=k-'0';
  37.       break;
  38.     }
  39.   }
  40.   for(;;){
  41.     k = my_getchar_unlocked();
  42.     if(k<'0'||k>'9'){
  43.       break;
  44.     }
  45.     x=x*10+k-'0';
  46.   }
  47.   if(m){
  48.     x=-x;
  49.   }
  50. }
  51. struct MY_WRITER{
  52.   char buf[1048576];
  53.   int s;
  54.   int e;
  55.   MY_WRITER(){
  56.     s = 0;
  57.     e = 1048576;
  58.   }
  59.   ~MY_WRITER(){
  60.     if(s){
  61.       fwrite_unlocked(buf, 1, s, stdout);
  62.     }
  63.   }
  64. }
  65. ;
  66. MY_WRITER MY_WRITER_VAR;
  67. void my_putchar_unlocked(int a){
  68.   if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
  69.     fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
  70.     MY_WRITER_VAR.s = 0;
  71.   }
  72.   MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
  73. }
  74. inline void wt_L(char a){
  75.   my_putchar_unlocked(a);
  76. }
  77. inline void wt_L(long long x){
  78.   int s=0;
  79.   int m=0;
  80.   char f[20];
  81.   if(x<0){
  82.     m=1;
  83.     x=-x;
  84.   }
  85.   while(x){
  86.     f[s++]=x%10;
  87.     x/=10;
  88.   }
  89.   if(!s){
  90.     f[s++]=0;
  91.   }
  92.   if(m){
  93.     my_putchar_unlocked('-');
  94.   }
  95.   while(s--){
  96.     my_putchar_unlocked(f[s]+'0');
  97.   }
  98. }
  99. template<class T> int coordcomp_L(int n, T arr[], int res[] = NULL, void *mem = wmem){
  100.   int i;
  101.   int k = 0;
  102.   pair<T,int>*r;
  103.   walloc1d(&r, n, &mem);
  104.   for(i=(0);i<(n);i++){
  105.     r[i].first = arr[i];
  106.     r[i].second = i;
  107.   }
  108.   sort(r, r+n);
  109.   if(res != NULL){
  110.     for(i=(0);i<(n);i++){
  111.       if(i && r[i].first != r[i-1].first){
  112.         k++;
  113.       }
  114.       res[r[i].second] = k;
  115.     }
  116.   }
  117.   else{
  118.     for(i=(0);i<(n);i++){
  119.       if(i && r[i].first != r[i-1].first){
  120.         k++;
  121.       }
  122.       arr[r[i].second] = k;
  123.     }
  124.   }
  125.   return k+1;
  126. }
  127. template<class T> struct fenwick{
  128.   int size;
  129.   int memory;
  130.   T*data;
  131.   void malloc(int mem);
  132.   void malloc(int mem, int fg);
  133.   void walloc(int mem, void **workMemory = &wmem);
  134.   void walloc(int mem, int fg, void **workMemory = &wmem);
  135.   void free(void);
  136.   void init(int N);
  137.   void add(int k, T val);
  138.   T get(int k);
  139.   T range(int a, int b);
  140.   int kth(T k);
  141. }
  142. ;
  143. int N;
  144. int W[200000];
  145. int r[200000];
  146. long long res[200000];
  147. fenwick<long long> f;
  148. int main(){
  149.   int i;
  150.   wmem = memarr;
  151.   rd(N);
  152.   {
  153.     int Lj4PdHRW;
  154.     for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){
  155.       rd(W[Lj4PdHRW]);
  156.     }
  157.   }
  158.   f.walloc(N+1,1);
  159.   coordcomp_L(N, W, r);
  160.   for(i=(0);i<(N);i++){
  161.     f.add(r[i], W[i]);
  162.     res[i] += f.range(r[i]+1, N);
  163.     if(i){
  164.       res[i] += res[i-1];
  165.     }
  166.   }
  167.   {
  168.     int RZTsC2BF;
  169.     if(N==0){
  170.       wt_L('\n');
  171.     }
  172.     else{
  173.       for(RZTsC2BF=(0);RZTsC2BF<(N-1);RZTsC2BF++){
  174.         wt_L(res[RZTsC2BF]);
  175.         wt_L(' ');
  176.       }
  177.       wt_L(res[RZTsC2BF]);
  178.       wt_L('\n');
  179.     }
  180.   }
  181.   return 0;
  182. }
  183. template<class T> void fenwick<T>::malloc(int mem){
  184.   memory = mem;
  185.   data = (T*)std::malloc(sizeof(T)*mem);
  186. }
  187. template<class T> void fenwick<T>::malloc(int mem, int fg){
  188.   memory = mem;
  189.   data = (T*)std::malloc(sizeof(T)*mem);
  190.   if(fg){
  191.     init(mem);
  192.   }
  193. }
  194. template<class T> void fenwick<T>::walloc(int mem, void **workMemory /* = &wmem*/){
  195.   memory = mem;
  196.   walloc1d(&data, mem, workMemory);
  197. }
  198. template<class T> void fenwick<T>::walloc(int mem, int fg, void **workMemory /* = &wmem*/){
  199.   memory = mem;
  200.   walloc1d(&data, mem, workMemory);
  201.   if(fg){
  202.     init(mem);
  203.   }
  204. }
  205. template<class T> void fenwick<T>::free(void){
  206.   memory = 0;
  207.   free(data);
  208. }
  209. template<class T> void fenwick<T>::init(int N){
  210.   size = N;
  211.   memset(data,0,sizeof(T)*N);
  212. }
  213. template<class T> void fenwick<T>::add(int k, T val){
  214.   while(k < size){
  215.     data[k] += val;
  216.     k |= k+1;
  217.   }
  218. }
  219. template<class T> T fenwick<T>::get(int k){
  220.   T res = 0;
  221.   while(k>=0){
  222.     res += data[k];
  223.     k = (k&(k+1))-1;
  224.   }
  225.   return res;
  226. }
  227. template<class T> T fenwick<T>::range(int a, int b){
  228.   if(b==-1){
  229.     b=size-1;
  230.   }
  231.   return get(b) - get(a-1);
  232. }
  233. template<class T> int fenwick<T>::kth(T k){
  234.   int i=0;
  235.   int j=size;
  236.   int c;
  237.   T v;
  238.   while(i<j){
  239.     c = (i+j)/2;
  240.     v = get(c);
  241.     if(v <= k){
  242.       i=c+1;
  243.     }
  244.     else{
  245.       j=c;
  246.     }
  247.   }
  248.   return i==size?-1:i;
  249. }
  250. // cLay varsion 20201031-1
  251.  
  252. // --- original code ---
  253. // int N, W[2d5];
  254. // int r[2d5];
  255. // ll res[2d5];
  256. // fenwick<ll> f;
  257. // {
  258. //   rd(N,W(N));
  259. //   f.walloc(N+1,1);
  260. //   coordcomp(N, W, r);
  261. //   rep(i,N){
  262. //     f.add(r[i], W[i]);
  263. //     res[i] += f.range(r[i]+1, N);
  264. //     if(i) res[i] += res[i-1];
  265. //   }
  266. //   wt(res(N));
  267. // }
  268.  
Time limit exceeded #stdin #stdout 5s 4516KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MGzmdA
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!