fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3.     using namespace std;
  4.     //#include "testlib.h"
  5.     #define ff first
  6.     #define ss second
  7.     #define mp make_pair
  8.     #define all(v) v.begin(),v.end()
  9.     #define int long long
  10.     #define ll long long
  11.     #define M 1000000007
  12.     #define inputarr(a,n) for(int i=0;i<n;++i) cin>>a[i]
  13.     #define GCD(m,n) __gcd(m,n)
  14.     #define LCM(m,n) m*(n/GCD(m,n))
  15.     #define mii  map<ll ,ll >
  16.     #define sz(a) (int)a.size()
  17.     #define msi  map<string,ll >
  18.     #define mis  map<ll int, string>
  19.     #define rep(a,b)    for(ll i=a;i<b;i++)
  20.     #define rep0(n)    for(ll i=0;i<n;i++)
  21.     #define repi(i,a,b) for(ll i=a;i<b;i++)
  22.     #define pb push_back
  23.     #define vi vector<ll>
  24.     #define mp make_pair
  25.     #define vs vector<string>
  26.     #define ppb pop_back
  27.     #define endl '\n'
  28.     #define asdf ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  29.     #define r0 return 0;
  30.     #define FORD(i, a, b) for (int i = (int) (a); i >= (int) (b); --i)
  31.     #define FORE(it, c) for (__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
  32.     #define inputoutput freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
  33.     #define input freopen("input.txt", "r", stdin);
  34.     #define Set(a, s) 4(a, s, sizeof (a))
  35.     #define FOR repi
  36.     #define pii pair<int,int>
  37.     #define REVERSE(v) reverse(ALL(v))
  38.     #define display(x) trav(a,x) cout<<a<<" ";cout<<endl
  39.     #define debug cerr<<"bhau"<<endl
  40.     #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  41.     template <typename Arg1>
  42.     void __f(const char* name, Arg1&& arg1){
  43.         std::cerr << name << " : " << arg1 << endl;
  44.     }
  45.     template <typename Arg1, typename... Args>
  46.     void __f(const char* names, Arg1&& arg1, Args&&... args){
  47.         const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  48.     }
  49.     ll max(ll a, ll b) { return (a > b)? a : b;}
  50.     int min(int a, int b) { return (a < b)? a : b;}
  51.     void amax(int &a,int b){a=max(a,b)%M; }
  52.     void amin(int &a,int b){ a=min(a,b)%M;}
  53.     void inc(int &a,int b){a=(a+b)%M;}
  54.     void dec(int &a,int b){a=(a-b+M)%M;}
  55.     const int N=2e5+100,inf=0;
  56.     int total[2*N];
  57.     int pre[2*N];
  58.     int suff[2*N];
  59.     int ans[2*N];
  60.     int n;
  61.     void build(){
  62.       for(int i=n-1;i>=0;i--) {total[i]=total[i<<1]+total[i<<1|1];pre[i]=max(pre[i<<1],total[i<<1]+pre[i<<1|1]);suff[i]=max(suff[i<<1|1],suff[i<<1]+total[i<<1|1]);ans[i]=max({ans[i<<1],ans[i<<1|1],pre[i<<1|1]+suff[i<<1]});}
  63.     }
  64.     void modify(int p,int x){
  65.       p+=n;
  66.       for(total[p]=suff[p]=pre[p]=ans[p]=x;p>1;p>>=1) {
  67.  
  68.         total[p>>1]=total[p]+total[p^1];
  69.         int right=max(p,p^1),left=min(p,p^1);
  70.         pre[p>>1]=max(pre[left],total[left]+pre[right]);
  71.         suff[p>>1]=max(suff[right],suff[left]+total[right]);
  72.         ans[p>>1]=max({ans[left],ans[right],pre[right]+suff[left]});
  73.         // trace(p>>1,p,p^1,total[p>>1],pre[p>>1],suff[p>>1],ans[p>>1]);
  74.       }
  75.     }
  76.     int query(int l,int r){
  77.       int tl,tr;tl=tr=0;
  78.       int pl,pr;
  79.       pl=pr=inf;
  80.       pr=inf;
  81.       int al,ar;
  82.       al=ar=inf;
  83.       int sl=inf,sr=inf;
  84.       for(l+=n,r+=n;l<r;l>>=1,r>>=1){
  85.         // trace(l,r);
  86.         if(l&1) {
  87.           al=max({al,ans[l],sl+pre[l]});
  88.           pl=max(pl,tl+pre[l]);
  89.           sl=max(suff[l],total[l]+sl);
  90.  
  91.           tl+=total[l];
  92.           l++;
  93.         }
  94.         if(r&1) {
  95.           --r;
  96.           ar=max({ar,ans[r],sr+pre[r]});
  97.           pr=max(pre[r],total[r]+pr);
  98.           sr=max(sr,tr+suff[r]);
  99.           tr+=total[r];
  100.         }
  101.         // trace(pl,pr,sl,sr,al,ar,tl,tr);
  102.       }
  103.       int res;
  104.       res=max({al,ar,pr+sl});
  105.       return res;
  106.     }
  107.  
  108.  
  109.      int solve()
  110.      {  
  111.         int q;cin>>n>>q;
  112.         rep0(n) cin>>total[i+n];
  113.         rep0(n) {pre[i]=suff[i]=ans[i]=inf;pre[n+i]=suff[n+i]=ans[n+i]=total[n+i];}
  114.         build();
  115.         while(q--){
  116.           int k,x;cin>>k>>x;k--;
  117.           modify(k,x);
  118.           cout<<query(0,n)<<endl;
  119.         }
  120.         r0   
  121.      }
  122.     signed main()
  123.     {   
  124.         asdf
  125.  
  126.         int t=1;
  127.         //cin>>t;
  128.         while(t--)
  129.         {
  130.             solve();
  131.         }     
  132.  
  133. }
Success #stdin #stdout 0s 4252KB
comments (?)
stdin
copy 
5 3
1 2 -3 5 -1
2 6
3 1
2 -2
stdout
copy 
9
13
6
https://ideone.com/W2obub
language:
C++14 (gcc 8.3)
created:
5 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!