Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //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
- //https://ru.stackoverflow.com/questions/806140/Что-такое-upper-bound-и-lower-bound-в-c-и-чем-они-отличаются
- #pragma warning(disable: 4996)
- #pragma warning(disable: 6031)
- #define _USE_MATH_DEFINES
- #include <iostream>
- #include <vector>
- #include <stack>
- #include <deque>
- #include <string>
- #include <algorithm>
- #include <functional>
- #include <queue>
- #include <cmath>
- #include <map>
- #include <limits>
- #include <iomanip>
- #include <list>
- #include <ctype.h>
- #include <set>
- #define watch(x) cout << (#x) << " is = " << (x) << endl;
- #define watchP(p) cout << (#p) << " x= " << (p.x) << " y= " << p.y << endl;
- #define max3(x1, x2, x3) max(max(x1, x2), x3);
- #define min3(x1, x2, x3) min(min(x1, x2), x3);
- #define max4(x1, x2, x3, x4) max(max(x1, x2), max(x3, x4));
- #define min4(x1, x2, x3, x4) min(min(x1, x2), min(x3, x4));
- #define max5(x1, x2, x3, x4, x5) max(x5, max(max(x1, x2), max(x3, x4)));
- #define min5(x1, x2, x3, x4, x5) min(x5, min(min(x1, x2), min(x3, x4)));
- #define ll long long
- #define ui unsigned int
- #define vi vector<ll>
- #define vd vector<double>
- #define vb vector<bool>
- #define vs vector<string>
- #define vvi vector<vector<ll>>
- #define vvd vector<vector<double>>
- #define ii pair<ll, ll>
- #define iii pair<ll, ii>
- #define vii vector<ii>
- #define mp make_pair
- #define EPS 1e-6
- #define INF 1e8
- #define DEV false
- using namespace std;
- vector<int> sumdels;
- #define ull unsigned long long
- vector<int> findLIS(vector<int> a) {
- vector<int> d = vector<int>(a.size(), -INT_MAX);
- *d.end() = INT_MAX;
- vector<int> pos = vector<int>(a.size());
- vector<int> prev = vector<int>(a.size());
- pos[0] = -1;
- int length = 0;
- for (int i = 0; i < a.size(); i++) {
- int j = upper_bound(d.begin(), d.end(), a[i]) - d.begin();
- //j--;
- //while (j - 1 >= 0 && d[j] == d[j + 1])
- // j--;
- if(d[j-1] >= a[i] && a[i] >= d[j]) {
- //if (d[j - 1] < a[i] && a[i] < d[j]) {
- d[j] = a[i];
- pos[j] = i;
- prev[i] = pos[j - 1];
- length = max(length, j);
- }
- }
- vector<int> answer = vector<int>();
- int p = pos[length];
- while (p != -1) {
- answer.push_back(a[p]);
- p = prev[p];
- }
- reverse(answer.begin(), answer.end());
- return answer;
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(NULL);
- #ifdef _DEBUG
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- #else
- //freopen("knights.in", "r", stdin);
- //freopen("knights.out", "w", stdout);
- #endif // !DEBUG
- string digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
- ll n;
- cin >> n;
- vector<int> bb = {5, 4, 3, 2, 1};
- vector<int>::iterator ender = (bb.end()-1);
- cout << *ender << endl;
- bb.pop_back();
- cout << *ender << endl;
- cout << *(bb.end()-1) << endl;
- cout << bb[bb.size()-1] << endl;
- cout << upper_bound(bb.begin(), bb.end(), 4) - bb.begin() << endl;
- /*
- vector<int> res = vector<int>(n);
- for (int i = 0; i < n; i++)
- cin >> res[i];
- res = findLIS(res);
- for (int i = 0; i < res.size(); i++)
- cout << res[i];
- */
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement