Guest User

Untitled

a guest
Sep 19th, 2017
286
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int n,m,q;
  6. long long a[100005],b[100005];
  7. long long sume[100005],sumo[100005],sum;
  8. vector<long long> v;
  9.  
  10. long long gete(int x,int y)
  11. {
  12.     if(!x)
  13.         return sume[y];
  14.     return sume[y]-sume[x-1];
  15. }
  16.  
  17. long long geto(int x,int y)
  18. {
  19.     if(!x)
  20.         return sumo[y];
  21.     return sumo[y]-sumo[x-1];
  22. }
  23.  
  24. long long query()
  25. {
  26.     int ind=lower_bound(v.begin(),v.end(),sum)-v.begin();
  27.     if(ind==v.size())
  28.         ind--;
  29.     long long ans=llabs(v[ind]-sum);
  30.     if(ind!=v.size()-1)
  31.         ans=min(ans,llabs(v[ind+1]-sum));
  32.     if(ind!=0)
  33.         ans=min(ans,llabs(v[ind-1]-sum));
  34.     return ans;
  35. }
  36.  
  37. int main()
  38. {
  39.     cin >> n >> m >> q;
  40.     int i;
  41.     for(i=0;i<n;i++)
  42.         cin >> a[i];
  43.     for(i=0;i<m;i++)
  44.         cin >> b[i];
  45.     for(i=0;i<m;i++)
  46.     {
  47.         if(i%2==0)
  48.             sume[i]+=b[i];
  49.         else
  50.             sumo[i]+=b[i];
  51.         if(i) {sume[i]+=sume[i-1]; sumo[i]+=sumo[i-1];}
  52.     }
  53.     for(i=0;i<n;i++)
  54.         sum+=a[i]*(i%2==0?1:-1);
  55.     for(i=0;i<=m-n;i++)
  56.     {
  57.         if(i%2==0)
  58.             v.push_back(gete(i,i+n-1)-geto(i,i+n-1));
  59.         else
  60.             v.push_back(geto(i,i+n-1)-gete(i,i+n-1));
  61.     }
  62.     sort(v.begin(),v.end());
  63.     cout << query() << endl;
  64.     while(q--)
  65.     {
  66.         int l,r,x;
  67.         cin >> l >> r >> x;
  68.         if((r-l)%2==0)
  69.         {
  70.             if(l%2) sum+=x;
  71.             else sum-=x;
  72.         }
  73.         cout << query() << endl;
  74.     }
  75. }
RAW Paste Data