[Toph] MSIS!

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : MSIS!
Source            : Toph
Category          : Data Structure, Policy Based Data Structure
Algorithm         : PBDS
Verdict           : Accepted

1. #include "bits/stdc++.h"  
2. #include "ext/pb_ds/assoc_container.hpp"  
3. #include "ext/pb_ds/tree_policy.hpp"  
4. #include "ext/rope"  
5.   
6. using namespace std;  
7. using namespace __gnu_pbds;  
8. using namespace __gnu_cxx;  
9.   
10. /* 
11. #pragma GCC optimize("O3") 
12. #pragma GCC optimize("unroll-loops") 
13. #pragma GCC target("avx,avx2,fma") 
14. */  
15.   
16. void trace(int x)                         { cerr << x; }  
17. void trace(long x)                        { cerr << x; }  
18. void trace(long long x)                   { cerr << x; }  
19. void trace(unsigned x)                    { cerr << x; }  
20. void trace(unsigned long x)               { cerr << x; }  
21. void trace(unsigned long long x)          { cerr << x; }  
22. void trace(float x)                       { cerr << x; }  
23. void trace(double x)                      { cerr << x; }  
24. void trace(long double x)                 { cerr << x; }  
25. void trace(char x)                        { cerr << '\'' << x << '\''; }  
26. void trace(const char *x)                 { cerr << '\"' << x << '\"'; }  
27. void trace(const string &x)               { cerr << '\"' << x << '\"'; }  
28. void trace(bool x)                        { cerr << (x ? "true" : "false"); }  
29.   
30. template <typename A, typename B>                         void trace(const pair <A, B> &x)         { cerr << '{'; trace(x.first); cerr << ','; trace(x.second); cerr << '}'; }  
31. template <typename A, typename B, typename C>             void trace(const tuple <A, B, C> &x)     { cerr << '{'; trace(get <0> (x)); cerr << ','; trace(get <1> (x)); cerr << ','; trace(get <2> (x)); cerr << '}'; }  
32. template <typename A, typename B, typename C, typename D> void trace(const tuple <A, B, C, D> &x)  { cerr << '{'; trace(get <0> (x)); cerr << ','; trace(get <1> (x)); cerr << ','; trace(get <2> (x)); cerr << ','; trace(get <3> (x)); cerr << '}'; }  
33. template <typename T>                                     void trace(const T &x)                   { int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), trace(i); cerr << "}"; }  
34. template <size_t N>                                       void trace(bitset <N> v)                 { cerr << '{'; for (size_t i = 0; i < N; i++) cerr << static_cast <char> ('0' + v[i]); cerr << '}'; }  
35. void _print()                                                                                      { cerr << "]\n"; }  
36. template <typename T, typename... V>                      void _print(T t, V... v)                 { trace(t); if (sizeof...(v)) cerr << ", "; _print(v...); }  
37.   
38. #ifndef ONLINE_JUDGE  
39.       #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)  
40. #else  
41.       #define debug(x...)  
42. #endif  
43.   
44. template <typename T> using ordered_set                = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;  
45. template <typename T1, typename T2> using ordered_map  = tree <T1, T2, less <T1>, rb_tree_tag, tree_order_statistics_node_update>;  
46.   
47. template <class T> bool MIN(T &a, T b)                 { return a > b ? (a = b, true) : false; }  
48. template <class T> bool MAX(T &a, T b)                 { return a < b ? (a = b, true) : false; }  
49.   
50. template <class T> T binaryExpo(T a, T p)              { if (p == 0) { return 1LL; } if (p == 1) { return a; } if (p & 1) { return a * binaryExpo(a, p - 1); } T ret = binaryExpo(a, p / 2); return ret * ret; }  
51. template <class T> T bigMod(T a, T p, T m)             { if (p == 0) { return 1LL % m; } if (p == 1) { return a % m; } if (p & 1) { return (a % m * bigMod(a, p - 1, m)) % m; } T ret = bigMod(a, p / 2, m) % m; return (ret * ret) % m; }  
52. template <class T> T modInv(T a, T m)                  { return bigMod(a, m - 2, m); }  
53.   
54. template <typename T> string num_str(T num)            { stringstream ss; ss << num; return ss.str(); }  
55. long long str_num(string s)                            { long long num; istringstream iss(s); iss >> num; return num; }  
56.   
57. inline long long ON(long long mask, int pos)           { return mask |= (1LL << pos); }  
58. inline long long OFF(long long mask, int pos)          { return mask &= ~(1LL << pos); }  
59. inline long long TOGGLE(long long mask, int pos)       { return mask ^= (1LL << pos); }  
60. inline bool CHECK(long long mask, int pos)             { return (bool)(mask >> pos & 1LL); }  
61.   
62. inline int ONE(long long mask)                         { return __builtin_popcountll(mask); }  
63. inline int LZERO(long long mask)                       { return 31 - __builtin_clzll(mask); };  
64. inline int TZERO(long long mask)                       { return __builtin_ctzll(mask); };  
65.   
66. //int dr[] = {+1, -1, +0, +0};                         // 4 Direction - DOWN, UP, RIGHT, LEFT  
67. //int dc[] = {+0, +0, +1, -1};  
68. int dr[] = {+0, +0, +1, -1, +1, +1, -1, -1};       // 8 Direction - RIGHT, LEFT, DOWN, UP, RIGHT-DOWN, LEFT-DOWN, UP-RIGHT, UP-LEFT  
69. int dc[] = {+1, -1, +0, +0, +1, -1, +1, -1};  
70. //int dr[] = {-1, +1, -2, -2, -1, +1, +2, +2};       // knight Moves  
71. //int dc[] = {-2, -2, -1, +1, +2, +2, +1, -1};  
72.   
73. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());  
74.   
75. #define ll              long long int  
76. #define ull             unsigned long long int  
77. #define endl            '\n'  
78. #define pii             pair <int, int>  
79. #define pll             pair <ll, ll>  
80. #define mk              make_pair  
81. #define ff              first  
82. #define ss              second  
83. #define all(a)          (a).begin(), (a).end()  
84. #define rall(a)         (a).rbegin(), (a).rend()  
85. #define eb              emplace_back  
86. #define pb              push_back  
87. #define pf              push_front  
88. #define allUpper(a)     transform(all(a), a.begin(), :: toupper)  
89. #define allLower(a)     transform(all(a), a.begin(), :: tolower)  
90. #define LINE            cerr << __LINE__ << " ";  
91. #define memo(a, b)      memset(a, b, sizeof a)  
92. #define ook             order_of_key  
93. #define fbo             find_by_order  
94.   
95. //#define int               long long int  
96.   
97. static const int maxn = 1e5 + 5;  
98. static const int logn = 19;  
99. static const long long MOD = 1e9 + 7;  
100. static const long long INF = 1e18;  
101.   
102. template <class Node_CItr, class Node_Itr, class Cmp_Fn, class _Alloc>  
103. struct my_update_policy {  
104.       virtual Node_CItr node_begin() const = 0;  
105.       virtual Node_CItr node_end() const = 0;  
106.       typedef long long int metadata_type;  
107.   
108.       long long prefix_max(long long x) {  
109.             long long ans = 0;  
110.             auto it = node_begin();  
111.             while (it != node_end()) {  
112.                   auto l = it.get_l_child();  
113.                   auto r = it.get_r_child();  
114.                   if (Cmp_Fn()(x, (*it)->first)) {  
115.                         it = l;  
116.                   }  
117.                   else {  
118.                         MAX(ans, (*it)->second);  
119.                         if (l != node_end()) {  
120.                               MAX(ans, l.get_metadata());  
121.                         }  
122.                         it = r;  
123.                   }  
124.             }  
125.             return ans;  
126.       }  
127.       void operator()(Node_Itr it, Node_CItr end_it) {  
128.             auto l = it.get_l_child();  
129.             auto r = it.get_r_child();  
130.             long long int lft = 0;  
131.             long long int rgt = 0;  
132.             if (l != node_end()) {  
133.                   lft = l.get_metadata();  
134.             }  
135.             if (r != node_end()) {  
136.                   rgt = r.get_metadata();  
137.             }  
138.             const_cast <long long int&> (it.get_metadata()) = max({lft, rgt, (*it)->second});  
139.       }  
140. };  
141.   
142. template <class T> using orderd_map = tree <T, T, less <T>, rb_tree_tag, my_update_policy>;  
143.   
144. signed main()  
145. {  
146.       ios_base::sync_with_stdio(false);  
147.       cin.tie(nullptr);  
148.       cout.tie(nullptr);  
149.       cout.precision(12);  
150.   
151.       #ifndef ONLINE_JUDGE  
152.           freopen("in.txt", "r", stdin);  
153.       #endif // ONLINE_JUDGE  
154.   
155.       int n;  
156.       cin >> n;  
157.       long long msis = 0;  
158.       orderd_map <ll> mp;  
159.       for (int i = 0; i < n; i++) {  
160.             long long x;  
161.             cin >> x;  
162.             long long maxi = x + mp.prefix_max(x - 1);  
163.             MAX(maxi, mp[x]);  
164.             mp.erase(mp.find(x));  
165.             mp.insert(mk(x, maxi));  
166.             MAX(msis, mp[x]);  
167.       }  
168.       cout << msis << endl;  
169.   
170.   
171.       #ifndef ONLINE_JUDGE  
172.             cerr << endl << "Time : " << 1.0 * clock() / CLOCKS_PER_SEC << " s." << endl;  
173.       #endif // ONLINE_JUDGE  
174.   
175.       return 0;  
176. }