Tuesday, July 14, 2020

[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. }  
 

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.