fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <string>
  5. #include <cstring>
  6. #include <vector>
  7. #include <set>
  8.  
  9. using namespace std;
  10.  
  11. const int N = 130005;
  12.  
  13. int n;
  14. long long a[N] , b[N];
  15. pair <long long,int> p[N];
  16.  
  17. int timer = 1;
  18. int root[N];
  19.  
  20. long long t[N * 30];
  21. int son1[N * 30] , son2[N * 30];
  22. long long sum1[N * 30] , sum2[N * 30] , sum[N * 30];
  23.  
  24. void build(int v,int s,int e){
  25.     if(s == e)return ;
  26.     int m = (s + e) / 2;
  27.     if(son1[v] == 0){
  28.         son1[v] = ++timer;
  29.         son2[v] = ++timer;
  30.     }
  31.     build(son1[v] , s , m);
  32.     build(son2[v] , m+1 , e);
  33. }
  34.  
  35. int update(int v,int s,int e,int pos){
  36.     int vv = ++timer;
  37.     if(s == e){
  38.         t[vv] = 1;
  39.         sum1[vv] = a[s];
  40.         sum2[vv] = b[s];
  41.         sum[vv] = (a[s] + b[s]) / 2;
  42.         return vv;
  43.     }
  44.     int m = (s + e) / 2;
  45.     if(pos <= m){
  46.         son2[vv] = son2[v];
  47.         son1[vv] = update(son1[v] , s , m , pos); 
  48.     }
  49.     else{
  50.         son1[vv] = son1[v];
  51.         son2[vv] = update(son2[v] , m+1 , e , pos); 
  52.     }
  53.     t[vv] = t[son1[vv]] + t[son2[vv]];
  54.     sum[vv] = sum[son1[vv]] + sum[son2[vv]];
  55.     sum1[vv] = sum1[son1[vv]] + sum1[son2[vv]];
  56.     sum2[vv] = sum2[son1[vv]] + sum2[son2[vv]];
  57.     return vv;
  58. }
  59.  
  60. long long get(int v,int s,int e,int l,int r,int id){
  61.     if(l > r)return 0;
  62.     if(s == l && e == r){
  63.         if(id == 0)return t[v];
  64.         if(id == 1)return sum1[v];
  65.         if(id == 2)return sum[v];
  66.         if(id == 3)return sum2[v];
  67.     }
  68.     int m = (s + e) / 2;
  69.     return get(son1[v] , s , m , l , min(r , m) , id) + get(son2[v] , m+1 , e , max(m+1 , l) , r , id);
  70. }
  71.  
  72. int main(){
  73.     scanf("%d",&n);
  74.     for(int i=1;i<=n;i++){
  75.         scanf("%lld",&a[i]);
  76.         a[i] *= 2;
  77.     }
  78.     for(int i=1;i<=n;i++){
  79.         scanf("%lld",&b[i]);
  80.         b[i] *= 2;
  81.     }
  82.     for(int i=1;i<=n;i++){
  83.         p[i] = make_pair(b[i] - a[i] , i);
  84.     }
  85.     sort(p + 1 , p + n + 1);
  86.     build(1 , 1 , n);
  87.     root[0] = 1;
  88.     for(int i=1;i<=n;i++){
  89.         root[i] = update(root[i - 1] , 1 , n , p[i].second);
  90.     }
  91.     int q;
  92.     scanf("%d",&q);
  93.     while(q--){
  94.         int l,r;
  95.         scanf("%d%d",&l,&r);
  96.         int x = (r - l + 1) / 3;
  97.         int ina = 1 , inb = n , ind1;
  98.         long long answ = 0;
  99.         while(ina <= inb){
  100.             int mid = (ina + inb) / 2;
  101.             long long T = get(root[mid] , 1 , n , l , r , 0);
  102.             if(T >= x){
  103.                 ind1 = mid;
  104.                 inb = mid - 1;
  105.             }
  106.             else{
  107.                 ina = mid + 1;
  108.             }
  109.         }
  110.         answ += get(root[ind1] , 1 , n , l , r , 1);
  111.         int ind2;
  112.         ina = 1;inb = n;
  113.         while(ina <= inb){
  114.             int mid = (ina + inb) / 2;
  115.             long long T = get(root[mid] , 1 , n , l , r , 0);
  116.             if(T >= 2 * x){
  117.                 ind2 = mid;
  118.                 inb = mid - 1;
  119.             }
  120.             else{
  121.                 ina = mid + 1;
  122.             }
  123.         }
  124.         answ += get(root[ind2] , 1 , n , l , r , 2) - get(root[ind1] , 1 , n , l , r , 2);
  125.         answ += get(root[n] , 1 , n , l , r , 3) - get(root[ind2] , 1 , n , l , r , 3);
  126.         printf("%lld",answ / 2);
  127.         if(answ % 2)printf(".5");
  128.         printf("\n");
  129.     }
  130.     return 0;
  131. }
Runtime error #stdin #stdout 0.18s 473728KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bk5Qag
language:
C++ 4.3.2 (gcc-4.3.2)
created:
7 years ago
visibility:
public

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!