fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. #include <iostream>
  5. #include <string.h>
  6. //-------------------------------------macros-----------------------------------------------
  7. #define ll long long int
  8. #define ull unsigned long long int
  9. #define ld long double
  10. #define color(array, value) memset(array, value, sizeof(array))
  11. #define colorDD(array, value) fill_n(*array, sizeof(array) / sizeof(**array), value);
  12. #define sz(x) ((ll)x.size())
  13. #define cerr(x) cout << #x << " = " << x << endl
  14. #define YES cout << "YES\n"
  15. #define NO cout << "NO\n"
  16. #define Yes cout << "Yes\n"
  17. #define No cout << "No\n"
  18. #define endl "\n"
  19. #define FOR(index, lower, upper) for (ll index = lower; index < upper; index++)
  20. #define FORD(index, upper, lower) for (ll index = upper; index > lower; index--)
  21. #define all(x) x.begin(), x.end()
  22. #define rall(x) x.rbegin(), x.rend()
  23. #define containsKey(map, key) (map.find(key) != map.end())
  24. #define umap unordered_map
  25. #define uset unordered_set
  26. #define CASE(x) cout << "Case " << x << ":" << endl;
  27. #define popcount(x) __builtin_popcount(x)
  28. #define pll pair<ll, ll>
  29. const ll MOD = 1e9 + 7;
  30. const ll A_MOD = 998244353;
  31. const ld EPS = 1e-7;
  32. const ld PI = acos(-1.0);
  33. const ll INF = 1e18;
  34.  
  35. /*------------------------------------Policy based data structures-------------------------------------------*/
  36. using namespace std;
  37. using namespace __gnu_pbds;
  38. template <class T>
  39. using oset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  40. /*-----------custom-hash------------*/
  41. struct custom_hash {
  42.     static uint64_t splitmix64(uint64_t x) {
  43.         x += 0x9e3779b97f4a7c15;
  44.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  45.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  46.         return x ^ (x >> 31);
  47.     }
  48.  
  49.     size_t operator()(uint64_t x) const {
  50.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  51.         return splitmix64(x + FIXED_RANDOM);
  52.     }
  53. };
  54. template <class T1, class T2>
  55. using pmap = gp_hash_table<T1, T2, custom_hash>;
  56. template <class T>
  57. using pset = unordered_set<T, custom_hash>;
  58. /*----------------------Graph Moves----------------*/
  59. const ll dx[] = {+0, +0, +1, -1, -1, +1, -1, +1}; // Kings Move L R D U
  60. const ll dy[] = {-1, +1, +0, +0, +1, +1, -1, -1}; // Kings Move
  61. // const ll dx[] = {-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
  62. // const ll dy[] = {-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
  63. /*------------------------------------------------*/
  64.  
  65. bool isBitSet(ll number, ll bit) {
  66.     return (number & (1ll << bit)) != 0;
  67. }
  68.  
  69. ll inverseBit(ll number, ll bit) {
  70.     return (number ^ (1ll << bit));
  71. }
  72.  
  73. ll ceil_div(ll a, ll b) {
  74.     return a / b + ((a ^ b) > 0 && a % b != 0);
  75. }
  76.  
  77. template <typename T>
  78. T square(T v) {
  79.     return v * v;
  80. }
  81. bool comp_second(pair<ll, ll> &a, pair<ll, ll> &b) {
  82.     if (a.second != b.second)
  83.         return a.second < b.second;
  84.     return a.first < b.first;
  85. }
  86. bool comp_first_reverse(pair<ll, ll> &a, pair<ll, ll> &b) {
  87.     if (a.first != b.first)
  88.         return a.first < b.first;
  89.     return a.second > b.second;
  90. }
  91. bool comp_second_reverse(pair<ll, ll> &a, pair<ll, ll> &b) {
  92.     if (a.second != b.second)
  93.         return a.second > b.second;
  94.     return a.first < b.first;
  95. }
  96.  
  97. ll __lcm(ll a, ll b) {
  98.     return (a / __gcd(a, b)) * b;
  99. }
  100.  
  101. struct Point {
  102.     ld x, y;
  103.     Point() : x(0.0), y(0.0) {}
  104.     Point(ld _x, ld _y) : x(_x), y(_y){};
  105. };
  106.  
  107. //-------------------------------------------- fast-io----------------------------------------
  108.  
  109. void HUTH() {
  110.     ios_base::sync_with_stdio(false);
  111.     cin.tie(NULL);
  112.     cout.tie(NULL);
  113. #ifndef ONLINE_JUDGE
  114.     freopen("input", "r", stdin);
  115.     freopen("output", "w", stdout);
  116. #endif
  117. }
  118.  
  119. //-----------------------------------------Operator overloads----------------------------------
  120. template <typename T1, typename T2> // cin >> pair<T1, T2>
  121. istream &operator>>(istream &istream, pair<T1, T2> &p) { return (istream >> p.first >> p.second); }
  122. template <typename T> // cin >> vector<T>
  123. istream &operator>>(istream &istream, vector<T> &v) {
  124.     for (auto &it : v)
  125.         cin >> it;
  126.     return istream;
  127. }
  128. template <typename T1, typename T2> // cout << pair<T1, T2>
  129. ostream &operator<<(ostream &ostream, const pair<T1, T2> &p) { return (ostream << p.first << " " << p.second); }
  130. template <typename T> // cout << vector<T>
  131. ostream &operator<<(ostream &ostream, const vector<T> &c) {
  132.     ll n = sz(c);
  133.     FOR(i, 0, n) {
  134.         cout << c[i] << ((i == n - 1) ? "" : " ");
  135.     }
  136.     return ostream;
  137. }
  138. template <typename T> // cout << unordered_set<T>
  139. ostream &operator<<(ostream &ostream, const unordered_set<T> &c) {
  140.     for (auto &it : c)
  141.         cout << it << " ";
  142.     return ostream;
  143. }
  144. template <typename T> // cout << ordered_set<T>
  145. ostream &operator<<(ostream &ostream, const set<T> &c) {
  146.     for (auto &it : c)
  147.         cout << it << " ";
  148.     return ostream;
  149. }
  150. istream &operator>>(istream &istream, Point &v) {
  151.     cin >> v.x >> v.y;
  152.     return istream;
  153. }
  154. //-----------------------------------------Operator overloads----------------------------------
  155. void solve(ll);
  156.  
  157. int main() {
  158.  
  159.     HUTH();
  160.  
  161.     ll T = 1ll;
  162.     // cin >> T;
  163.     FOR(i, 1, T + 1) {
  164.         solve(i);
  165.     }
  166. }
  167. const ll N = (1e5 + 5);
  168. pair<int, int> seg_tree[4 * N];
  169. pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
  170.     if (a.first > b.first)
  171.         return a;
  172.     else if (a.first < b.first)
  173.         return b;
  174.     return make_pair(a.first, ((ll)a.second + b.second) % MOD);
  175. }
  176. pair<int, int> query(ll node, ll left, ll right, ll start, ll end) {
  177.     if (left > end || right < start)
  178.         return make_pair(-1, 0);
  179.     if (left <= start && right >= end) {
  180.         return seg_tree[node];
  181.     }
  182.     ll mid = start + (end - start) / 2;
  183.     return merge(query(2 * node, left, right, start, mid), query(2 * node + 1, left, right, mid + 1, end));
  184. }
  185. void update(ll node, ll index, ll start, ll end, pair<int, int> val) {
  186.     if (start == end) {
  187.         if (val.first == seg_tree[node].first) {
  188.             ll ans = seg_tree[node].second;
  189.             ans += val.second;
  190.             ans %= MOD;
  191.             seg_tree[node].second = ans;
  192.             return;
  193.         } else {
  194.             seg_tree[node] = val;
  195.         }
  196.         return;
  197.     }
  198.     ll mid = start + (end - start) / 2;
  199.     if (index <= mid) {
  200.         update(2 * node, index, start, mid, val);
  201.     } else {
  202.         update(2 * node + 1, index, mid + 1, end, val);
  203.     }
  204.     seg_tree[node] = merge(seg_tree[2 * node], seg_tree[2 * node + 1]);
  205. }
  206. void compress_coordinate(vector<int> &a, pmap<int, int> &mp) {
  207.     vector<int> sorted(a);
  208.     sort(all(sorted));
  209.     int idx = 1;
  210.     for (auto &e : sorted) {
  211.         if (!containsKey(mp, e)) {
  212.             mp[e] = idx++;
  213.         }
  214.     }
  215.     for (int i = 0; i < sz(a); i++) {
  216.         a[i] = mp[a[i]];
  217.     }
  218. }
  219. void solve(ll TC) {
  220.     int n;
  221.     cin >> n;
  222.     vector<int> vc(n);
  223.     cin >> vc;
  224.     FOR(i, 0, N) {
  225.         seg_tree[i] = make_pair(0, 0);
  226.     }
  227.     pmap<int, int> mp;
  228.     compress_coordinate(vc, mp);
  229.     int ansl = 0, ansn = 0;
  230.     for (int i = 0; i < n; i++) {
  231.         auto res = query(1, 0, vc[i] - 1, 0, N);
  232.         if (res.first + 1 > ansl) {
  233.             ansl = res.first + 1;
  234.             ansn = max(1, res.second);
  235.         } else if (res.first + 1 == ansl) {
  236.             ll nans = ansn;
  237.             nans += res.second;
  238.             nans %= MOD;
  239.             ansn = nans;
  240.         }
  241.         update(1, vc[i], 0, N, make_pair(res.first + 1, max(1, res.second)));
  242.     }
  243.     cout << ansl << " " << ansn << endl;
  244. }
  245.  
  246. /*
  247.  itne me hi thakk gaya vro?
  248.  never compare your failure with other’s success.(which you are doing ri8 now)
  249.  
  250.  read question
  251.  rethink your approach
  252.  dont put --> n <-- in every for loop
  253.  consider case = 0
  254.  
  255.  Expert before 2023
  256. */
Success #stdin #stdout 0.01s 6272KB
comments (?)
stdin
copy 
5
1 3 2 5 4
stdout
copy 
3 4
https://ideone.com/cj9soG
problem HMLIS, based on SPOJ submission 30831912 (CPP14), 2023-02-08 11:56:38
language:
C++14 (gcc 8.3)
created:
1 year 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!