daily pastebin goal
64%
SHARE
TWEET

Spoj kgss maximum sum

sleepy_coder Mar 23rd, 2019 (edited) 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/tree_policy.hpp>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/detail/standard_policies.hpp>
  5. using namespace   std;
  6. using namespace __gnu_cxx;
  7. using namespace __gnu_pbds;
  8.  
  9. typedef pair<int, int> pii; typedef long long ll; typedef pair<ll, ll> pll;
  10. typedef vector<int> vi; typedef vector<ll> vl; typedef vector<pii> vii; typedef vector<pll> vll;
  11. typedef map<ll, ll> mii; typedef map<string, ll> msi; typedef vector< vi > vvi;
  12.  
  13. #define     sz                 size()
  14. #define     pb                 push_back
  15. #define     inf                (1<<30)
  16. #define     mod                (1000000007)
  17. #define     pi                 (acos(-1.0))
  18. #define     mem(a,b)           memset((a), (b), sizeof(a));
  19. #define     fast_io            ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  20. #define     what_is(x)         cerr << #x << " is " << x << endl;
  21. #define     rep(i, n)          for(__typeof(n) i=0; i<(n); i++)
  22. #define     foab(i, a, b)      for(__typeof(b) i=(a); i<=(b); i++)
  23. #define     foba(i, a, b)      for(__typeof(b) i=(b); i>=(a); i--)
  24. #define     foch(it, l)        for(__typeof((l).begin()) it = begin(l);  it != end(l); it++)
  25. #define     d_value(x)         cout<<fixed<<setprecision(x);
  26. #define     file_io            {                                        \
  27.                                     freopen("input.txt", "r", stdin);   \
  28.                                     freopen("output.txt", "w", stdout); \
  29.                                }
  30. #define error(args...) {                                                            \
  31.         string _s = #args; replace(_s.begin(), _s.end(), ',', ' ');                 \
  32.         stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);    \
  33.         }
  34.  
  35. void err(istream_iterator<string> it) {}                 template<typename T, typename... Args>
  36. void err(istream_iterator<string> it, T a, Args... args) { cerr << *it << " = " << a << endl; err(++it, args...); }
  37.  
  38. inline ll bigMul(ll a,ll b,ll m){
  39.     ll result = 0; a %= m;
  40.     while(b) { if(b&1LL) result=(result+a)%m; a=(a+a)%m; b>>=1; }
  41.     return result;
  42. }
  43.  
  44. ll bigMod(ll b, ll e, ll m){
  45.     if(!e)return 1%m;
  46.     if(!(e&1LL)){ ll y = bigMod(b, e>>1LL, m); return bigMul(y, y, m); }
  47.     ll z = bigMod(b, e-1, m); return (bigMul(b%m, z, m));
  48. }
  49.  
  50. /**Define BitWise operation**/
  51. #define     checkBit(n, pos)            (n & (1<<(pos)))
  52. #define     bitOn(n, pos)               (n | (1<<(pos)))
  53. #define     bitOff(n, pos)              (n & ~(1<<(pos)))
  54. inline void printBits(int n){ if(n >= 2)printBits(n/2); cout<<(n&1); }
  55. inline int countOnes(int n) { int r=0; while(n && ++r) n -= n&(-n); return r; }
  56.  
  57. template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  58. template <typename T>
  59. string toString(T n) { stringstream ss; ss << n; return ss.str(); }
  60. template< typename T >
  61. T exEuclid(T a, T b, T& x, T& y) {
  62.     if(!b){ x = 1, y = 0; return a; }
  63.     T x1, y1, temp = exEuclid<T>(b, a%b, x1, y1);
  64.     x = y1, y = x1 - y1*(a/b);
  65.     return temp;
  66. }
  67. template< typename T >
  68. inline T modInverse(T a, T m){ T x, y; T g = exEuclid<T>(a, m, x, y); if(g != 1){ return -1; } else{ return (x%m + m)%m; } }
  69. template<typename T> ostream&
  70. operator<<(ostream& os, const vector<T> &t) { ll n = t.size(); rep(i, n) os<<t[i]<<" "; return os; }
  71. template<typename T,typename TT>
  72. ostream& operator<<(ostream &os, const pair<T,TT> &t) { return os<<"("<<t.first<<","<<t.second<<")"; }
  73.  
  74. enum COLOR{ white=1 , grey=2 , black=3, red = 4, green = 5, blue = 6 };
  75.  
  76. vii dir_4 {{1,0}, {0,1}, {-1,0}, {0,-1}};
  77. vii dir_8 {{0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}};
  78. vii dir_knight {{2,1}, {1,2}, {-1,2}, {-2,1}, {-2,-1}, {-1,-2}, {1,-2}, {2,-1}};
  79. //-------------- ---------------- ----------------- --------------- ------------ ----------
  80.  
  81.  
  82.  
  83. //This is a Segment Tree Data structure for Range Query, Point Update
  84. class SegmentTree{
  85.     int* ara;
  86.     pii *tree;//{max, indx}
  87. public:
  88.  
  89.     explicit SegmentTree(int n, const int _ara[]){
  90.         ara = new int[n+1], tree = new pii[4*n+1];
  91.         foab(i, 1, n){
  92.             ara[i] = _ara[i-1];
  93.         }
  94.     }
  95.  
  96.     void init(const int& pos, const int& begin, const int& end){
  97.         if(begin == end){//leaf node
  98.             tree[pos] = {ara[end], end};
  99.         }else{//internal node
  100.             init(pos<<1, begin, (begin+end)>>1);
  101.             init((pos<<1)+1, ((begin+end)>>1)+1, end);
  102.             tree[pos] = tree[pos<<1].first > tree[(pos<<1)+1].first? tree[pos<<1] : tree[(pos<<1)+1];
  103.         }
  104.     }
  105.  
  106.     void update(const int& pos, const int& begin, const int& end, const int& indx, const int& newVal){
  107.         if(end < indx || indx < begin){//out of boundary
  108.             return;
  109.         }else if(indx<=begin && indx>=end){//relevant segment(index)
  110.             tree[pos].first = newVal;
  111.         }else{//partial overlap
  112.             update(pos<<1, begin, (begin+end)>>1, indx, newVal);
  113.             update((pos<<1)+1, ((begin+end)>>1)+1, end, indx, newVal);
  114.             tree[pos] = tree[pos<<1].first > tree[(pos<<1)+1].first? tree[pos<<1] : tree[(pos<<1)+1];
  115.         }
  116.     }
  117.  
  118.     pii query(const int& pos, const int& begin, const int& end, const int& i, const int& j){
  119.         if(i > j)return {0, -1};
  120.         if(i<=begin && end<=j){//relevant segment
  121.             return tree[pos];
  122.         }else if(j<begin || i>end){//out of boundary
  123.             return {0, -1};
  124.         }else{//partial overlap
  125.             pii left = query(pos<<1, begin, (begin+end)>>1, i, j);
  126.             pii right = query((pos<<1)+1, ((begin+end)>>1)+1, end, i, j);
  127.             if(left.first > right.first)return left;
  128.             else return right;
  129.         }
  130.     }
  131.  
  132.     virtual ~SegmentTree(){
  133.         delete [] ara;
  134.         delete [] tree;
  135.         ara = nullptr, tree = nullptr;
  136.     }
  137. };
  138.  
  139.  
  140. int main(int argc, char** argv) {
  141. #ifdef LOCAL
  142.     file_io
  143. #endif
  144.     //d_value(20);
  145.     fast_io
  146.  
  147.     int n; cin>>n;
  148.     int ara[n]; rep(i, n)cin>>ara[i];
  149.     SegmentTree tumi(n, ara);
  150.     tumi.init(1, 1, n);
  151.  
  152.     int q; cin>>q;
  153.     while(q--){
  154.         char ch; int x, y;
  155.         cin>>ch>>x>>y;
  156.         if(ch == 'U'){
  157.             tumi.update(1, 1, n, x, y);
  158.         }else{
  159.             pii f = tumi.query(1, 1, n, x, y);
  160.             pii a = tumi.query(1, 1, n, x, f.second-1);
  161.             pii b = tumi.query(1, 1, n, f.second+1, y);
  162.             a.first > b.first? f.first+=a.first: f.first+=b.first;
  163.             cout<<f.first<<endl;
  164.         }
  165.     }
  166.    
  167.  
  168.     return 0;
  169. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top