Advertisement
Pearlfromsu

fef

Apr 4th, 2022
968
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 3.23 KB | None | 0 0
  1. //https://neerc.ifmo.ru/wiki/index.php?title=Задача_о_наибольшей_возрастающей_подпоследовательности#.D0.A0.D0.B5.D1.88.D0.B5.D0.BD.D0.B8.D0.B5_.D0.B7.D0.B0_O.28N_log_N.29
  2. //https://ru.stackoverflow.com/questions/806140/Что-такое-upper-bound-и-lower-bound-в-c-и-чем-они-отличаются
  3.  
  4. #pragma warning(disable: 4996)
  5. #pragma warning(disable: 6031)
  6.  
  7. #define _USE_MATH_DEFINES
  8.  
  9. #include <iostream>
  10. #include <vector>
  11. #include <stack>
  12. #include <deque>
  13. #include <string>
  14. #include <algorithm>
  15. #include <functional>
  16. #include <queue>
  17. #include <cmath>
  18. #include <map>
  19. #include <limits>
  20. #include <iomanip>
  21. #include <list>
  22. #include <ctype.h>
  23. #include <set>
  24.  
  25.  
  26. #define watch(x) cout << (#x) << "   is = " << (x) << endl;
  27. #define watchP(p) cout << (#p) << "    x= " << (p.x) << "  y= " << p.y << endl;
  28. #define max3(x1, x2, x3) max(max(x1, x2), x3);
  29. #define min3(x1, x2, x3) min(min(x1, x2), x3);
  30. #define max4(x1, x2, x3, x4) max(max(x1, x2), max(x3, x4));
  31. #define min4(x1, x2, x3, x4) min(min(x1, x2), min(x3, x4));
  32. #define max5(x1, x2, x3, x4, x5) max(x5, max(max(x1, x2), max(x3, x4)));
  33. #define min5(x1, x2, x3, x4, x5) min(x5, min(min(x1, x2), min(x3, x4)));
  34.  
  35. #define ll long long
  36. #define ui unsigned int
  37. #define vi vector<ll>
  38. #define vd vector<double>
  39. #define vb vector<bool>
  40. #define vs vector<string>
  41. #define vvi vector<vector<ll>>
  42. #define vvd vector<vector<double>>
  43. #define ii pair<ll, ll>
  44. #define iii pair<ll, ii>
  45. #define vii vector<ii>
  46. #define mp make_pair
  47.  
  48.  
  49.  
  50. #define EPS 1e-6
  51. #define INF 1e8
  52.  
  53. #define DEV false
  54.  
  55. using namespace std;
  56.  
  57. vector<int> sumdels;
  58.  
  59. #define ull unsigned long long
  60.  
  61. vector<int> findLIS(vector<int> a) {
  62.     vector<int> d = vector<int>(a.size(), -INT_MAX);
  63.     *d.end() = INT_MAX;
  64.     vector<int> pos = vector<int>(a.size());
  65.     vector<int> prev = vector<int>(a.size());
  66.     pos[0] = -1;
  67.     int length = 0;
  68.     for (int i = 0; i < a.size(); i++) {
  69.         int j = upper_bound(d.begin(), d.end(), a[i]) - d.begin();
  70.         //j--;
  71.         //while (j - 1 >= 0 && d[j] == d[j + 1])
  72.         //  j--;
  73.         if(d[j-1] >= a[i] && a[i] >= d[j]) {
  74.         //if (d[j - 1] < a[i] && a[i] < d[j]) {
  75.             d[j] = a[i];
  76.             pos[j] = i;
  77.             prev[i] = pos[j - 1];
  78.             length = max(length, j);
  79.         }
  80.     }
  81.  
  82.     vector<int> answer = vector<int>();
  83.     int p = pos[length];
  84.     while (p != -1) {
  85.         answer.push_back(a[p]);
  86.         p = prev[p];
  87.     }
  88.     reverse(answer.begin(), answer.end());
  89.     return answer;
  90. }
  91.  
  92. int  main() {
  93.     ios::sync_with_stdio(false);
  94.     cin.tie(NULL);
  95.  
  96. #ifdef _DEBUG
  97.     //freopen("input.txt", "r", stdin);
  98.     //freopen("output.txt", "w", stdout);
  99. #else
  100.     //freopen("knights.in", "r", stdin);
  101.     //freopen("knights.out", "w", stdout);
  102. #endif // !DEBUG
  103.  
  104.     string digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  105.     ll n;
  106.     cin >> n;
  107.  
  108.     vector<int> bb = {5, 4, 3, 2, 1};
  109.     vector<int>::iterator ender = (bb.end()-1);
  110.     cout << *ender << endl;
  111.     bb.pop_back();
  112.     cout << *ender << endl;
  113.  
  114.     cout << *(bb.end()-1) << endl;
  115.     cout << bb[bb.size()-1] << endl;
  116.     cout << upper_bound(bb.begin(), bb.end(), 4) - bb.begin() << endl;
  117.     /*
  118.     vector<int> res = vector<int>(n);
  119.     for (int i = 0; i < n; i++)
  120.         cin >> res[i];
  121.     res = findLIS(res);
  122.     for (int i = 0; i < res.size(); i++)
  123.         cout << res[i];
  124.         */
  125.     return 0;
  126. }
  127.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement