Daffodil International University
Problem Link
//Please follow from main function
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<bits/stdc++.h> | |
| using namespace std; | |
| /// Typedef | |
| typedef long long ll; | |
| typedef unsigned long ul; | |
| typedef unsigned long long ull; | |
| typedef vector<int> vi; | |
| typedef vector<vi> vvi; | |
| typedef vector<ll> vll; | |
| typedef pair<int,int> pii; | |
| typedef pair<ll,ll> pll; | |
| typedef vector< pii > vii; | |
| #define loop(i, y) for(int i=0; i<int(y); i++) | |
| #define FOR(i, x, y) for(int i=int(x); i<=int(y); i++) | |
| #define READ(f) freopen(f, "r", stdin) | |
| #define WRITE(f) freopen(f, "w", stdout) | |
| #define FastIO ios_base::sync_with_stdio(false) | |
| #define sci(x) scanf("%d", &x) | |
| #define scii(x, y) scanf("%d %d", &x, &y) | |
| #define sciii(x, y, z) scanf("%d %d %d", &x, &y, &z) | |
| #define scl(x) scanf("%lld", &x) | |
| #define scll(x, y) scanf("%lld %lld", &x, &y) | |
| #define sclll(x, y, z) scanf("%lld %lld %lld", &x, &y, &z) | |
| /// Constants | |
| #define mx 100001 | |
| #define inf 1<<29 // 536,870,912 | |
| struct segtree{ | |
| ll sum, maxi, suffix, prefix; | |
| }tree[mx*4]; | |
| ll arr[mx]; | |
| segtree combine(segtree l, segtree r){ | |
| segtree temp; | |
| temp.sum=l.sum+r.sum; | |
| temp.prefix=max(l.prefix,l.sum+r.prefix); | |
| temp.suffix=max(r.suffix, r.sum+l.suffix); | |
| temp.maxi=max(max(l.maxi,r.maxi),l.suffix+r.prefix); | |
| return temp; | |
| } | |
| segtree min_data(){ | |
| segtree temp; | |
| temp.sum=0; | |
| temp.prefix=-inf; | |
| temp.suffix=-inf; | |
| temp.maxi=-inf; | |
| return temp; | |
| } | |
| segtree makedata(int value){ | |
| segtree temp; | |
| temp.sum=temp.prefix=temp.suffix=temp.maxi=value; | |
| return temp; | |
| } | |
| void init(ll node, ll s, ll e){ | |
| if(s==e){ | |
| tree[node]=makedata(arr[s]); | |
| return; | |
| } | |
| ll lft=node*2; | |
| ll rft=lft+1; | |
| ll mid=(s+e)/2; | |
| init(lft,s,mid); | |
| init(rft,mid+1, e); | |
| tree[node]=combine(tree[lft],tree[rft]); | |
| } | |
| segtree query(ll node, ll s, ll e, ll i, ll j){ | |
| if(i>e || j<s || s>e)return min_data(); | |
| if(s==i && j==e){ | |
| return tree[node]; | |
| } | |
| ll lft=(node*2); | |
| ll rft=lft+1; | |
| ll mid=(s+e)/2; | |
| return combine(query(lft,s,mid,i,min(mid,j)),query(rft,mid+1,e,max(mid+1,i),j)); | |
| } | |
| int main() | |
| { | |
| FastIO; | |
| #ifdef online | |
| clock_t tstart = clock(); | |
| READ("input.txt"); | |
| WRITE("output.txt"); | |
| #endif // online | |
| ll n; | |
| scl(n); | |
| FOR(i, 1, n){ | |
| ll x; | |
| scl(x); | |
| arr[i]=x; | |
| } | |
| init(1,1,n); | |
| ll q; | |
| scl(q); | |
| while(q--){ | |
| ll i, j; | |
| scll(i, j); | |
| segtree ans=query(1,1,n,i,j); | |
| cout<<ans.maxi<<endl; | |
| } | |
| return 0; | |
| } |
0 Comments