fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5.  
  6. const int N = 1e6 + 5;
  7. int n , q;
  8. int a[N] , pre[N];
  9.  
  10. main()
  11. {
  12.     ///freopen("KHAITHAC.INP","r",stdin);
  13.     ios::sync_with_stdio(0);
  14.     cin.tie(0);
  15.  
  16.     cin >> n >> q;
  17.     for(int i = 1 ; i <= n ; i++)
  18.     {
  19.         cin >> a[i];
  20.         pre[i] = pre[i - 1] + a[i];
  21.     }
  22.  
  23.     while(q--)
  24.     {
  25.         int u , v;
  26.         cin >> u >> v;
  27.         int S = pre[v] - pre[u - 1];
  28.         /// S1: [u,x] (u <= x <= v)
  29.         /// S1: pre[x] - pre[u - 1] <= S / 2
  30.         /// S1: pre[x] <= S / 2 + pre[u - 1]
  31.         int C = S / 2 + pre[u - 1];
  32.  
  33.         int l = u , r = v , ans = u - 1;
  34.         while(l <= r)
  35.         {
  36.             int mid = (l + r) / 2;
  37.             if(pre[mid] <= C)
  38.             {
  39.                 l = mid + 1;
  40.                 ans = mid;
  41.             }
  42.             else
  43.                 r = mid - 1;
  44.         }
  45.         int kq = 1e18;
  46.         /// [u,ans]
  47.  
  48.         if(ans != u - 1)
  49.         {
  50.             int S1 = (pre[ans] - pre[u - 1]);
  51.             int S2 = S - S1;
  52.             kq = min(kq , abs(S1 - S2));
  53.         }
  54.  
  55.         /// [u,ans + 1]
  56.         if(ans + 1 <= v)
  57.         {
  58.             int S1 = (pre[ans + 1] - pre[u - 1]);
  59.             int S2 = S - S1;
  60.             kq = min(kq , abs(S1 - S2));
  61.         }
  62.         cout << kq << "\n";
  63.     }
  64.  
  65.  
  66. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Thtey6
language:
C++14 (gcc 8.3)
created:
2 days 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!