fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. using namespace std;
  5.  
  6. const int N = 1<<19;
  7. const int TREE_SIZE = N<<2;
  8.  
  9. struct tree_node {
  10.     int *a,n;
  11.     tree_node(): n(0) {}
  12.     tree_node(int k) {
  13.         n=k;
  14.         a=(int*)malloc((sizeof(int)*k));
  15.     }
  16. };
  17.  
  18. struct merge_max {
  19.     pair < int, int > operator ()(const pair < int, int > &a, const pair < int, int > &b) const {
  20.         return max(a,b);
  21.     }
  22. };
  23.  
  24. template < class T, class MERGE >
  25. struct sparse_table {
  26.         MERGE merge;
  27.         int n,offset;
  28.         T **st;
  29.         int *log;
  30.         template < class CONTAINER >
  31.         void initialize(CONTAINER arr, int k, int base=1) {
  32.             int current_log=0,i,j;
  33.             offset=(base^1);
  34.             n=k;
  35.             log=(int*)malloc((sizeof(int)*(n+1)));
  36.             st=(T**)malloc((sizeof(T*)*(n+1)));
  37.             for(i=0;i<=n;i++) {
  38.                 while((1<<(1+current_log))<=i) ++current_log;
  39.                 log[i]=current_log;
  40.             }
  41.             for(i=1;i<=n;i++) st[i]=(T*)malloc((sizeof(T)*(log[n]+1)));
  42.             for(i=1;i<=n;i++) st[i][0]=arr[i-offset];
  43.             for(j=1;(1<<j)<=n;j++) for(i=1;i+(1<<j)-1<=n;i++) st[i][j]=merge(st[i][j-1],st[i+(1<<(j-1))][j-1]);
  44.         }
  45.         T query(int l, int r) {
  46.             l+=offset;
  47.             r+=offset;
  48.             int k=log[r-l+1];
  49.             return merge(st[l][k],st[r-(1<<k)+1][k]);
  50.         }
  51. };
  52.  
  53. int tests,current_case;
  54. int n,arr[N];
  55. tree_node tree[TREE_SIZE];
  56. long long ans;
  57. sparse_table < pair < int, int >, merge_max > rmq;
  58. pair < int, int > a[N];
  59.  
  60. void message(int current_case) {
  61.     fprintf(stderr, "Case %d solved!\n", current_case);
  62. }
  63.  
  64. inline tree_node merge_them(tree_node a, tree_node b) {
  65.     tree_node ans(a.n+b.n);
  66.     int i=0,j=0,idx=0;
  67.     while(i<a.n && j<b.n) {
  68.         if(a.a[i]<=b.a[j]) ans.a[idx++]=a.a[i++];
  69.         else ans.a[idx++]=b.a[j++];
  70.     }
  71.     while(i<a.n) ans.a[idx++]=a.a[i++];
  72.     while(j<b.n) ans.a[idx++]=b.a[j++];
  73.     return ans;
  74. }
  75.  
  76. inline void build_tree(int a, int b, int node) {
  77.     if(a>b) return;
  78.     if(a==b) {
  79.         tree[node]=tree_node(1);
  80.         tree[node].a[0]=arr[a];
  81.         return;
  82.     }
  83.     build_tree(a,(a+b)>>1,node<<1);
  84.     build_tree(((a+b)>>1)+1,b,(node<<1)|1);
  85.     tree[node]=merge_them(tree[node<<1],tree[(node<<1)|1]);
  86. }
  87.  
  88. inline int query_tree(int a, int b, int i, int j, int node, int value) {
  89.     if(a>b || a>j || b<i) return 0;
  90.     if(a>=i && b<=j) {
  91.         //if(value>=tree[node].a[tree[node].n-1]) return 0;
  92.         int left,right,middle;
  93.         left=-1;
  94.         right=tree[node].n;
  95.         while(right-left>1) {
  96.             middle=(left+right)>>1;
  97.             if(value<tree[node].a[middle]) right=middle;
  98.             else left=middle;
  99.         }
  100.         return tree[node].n-right;
  101.     }
  102.     return query_tree(a,(a+b)>>1,i,j,node<<1,value)+query_tree(((a+b)>>1)+1,b,i,j,(node<<1)|1,value);
  103. }
  104.  
  105. int query(int l, int r, int k) {
  106.     if(l>r) return 0;
  107.     return r-l+1-query_tree(1,n,l,r,1,k);
  108. }
  109.  
  110. void solve(int from, int to) {
  111.     if(from>=to) return;
  112.     pair < int, int > curr=rmq.query(from,to);
  113.     int i,left=curr.second-from,right=to-curr.second;
  114.     if(left<right) {
  115.         for(i=from;i<=curr.second;i++) {
  116.             ans+=query(curr.second+1,to,curr.first/arr[i]);
  117.         }
  118.         for(i=from;i<curr.second;i++) if(arr[i]==1) ++ans;
  119.     }
  120.     else {
  121.         for(i=curr.second;i<=to;i++) {
  122.             ans+=query(from,curr.second-1,curr.first/arr[i]);
  123.         }
  124.         for(i=curr.second+1;i<=to;i++) if(arr[i]==1) ++ans;
  125.     }
  126.     solve(from,curr.second-1);
  127.     solve(curr.second+1,to);
  128. }
  129.  
  130. int main() {
  131.     //ios_base::sync_with_stdio(false);
  132.     //cin.tie(NULL);
  133.     int i;
  134.  
  135.     tests=1;
  136.     //scanf("%d", &tests);
  137.     for(current_case=1;current_case<=tests;current_case++) {
  138.         scanf("%d", &n);
  139.         for(i=1;i<=n;i++) scanf("%d", &arr[i]),a[i]=make_pair(arr[i],i);
  140.         rmq.initialize(a,i);
  141.         ans=0;
  142.         build_tree(1,n,1);
  143.         solve(1,n);
  144.         printf("%lld\n", ans);
  145.         message(current_case);
  146.     }
  147.  
  148.     return 0;
  149. }
  150.  
Success #stdin #stdout #stderr 0s 26024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
stderr
copy 
Case 1 solved!
https://ideone.com/KVmgQl
language:
C++14 (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!