Аврора Интенсив день2

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include <cmath>
#include <math.h>
#include <algorithm>
#include <map>
#include <vector>
#include <utility>
#include <set>
#include <string>
#include <cstring>
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <bitset>
#include <cassert>
#include <functional>
//#include <intrin.h>
#include <stack>
#include <thread>
using namespace std;
//typedef long long ll;
#define ll long long
#define ld long double

const long long mod = 1000000007;

#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)>(y)?(x):(y))
#define PI 3.14159265358979323846
#define ABS(a) ((a)<0?-(a):(a))
template <typename T> inline T gcd(T a, T b) {
    while (b) { a %= b; swap(a, b); }
    return a;
}
long long fastpow(long long a, long long n)
{
    auto mult = a;
    long long res = 1;
    while (n)
    {
        if (n & 1)
            res *= mult;
        mult *= mult;
        n >>= 1;
    }
    return res;
}


void PrefSum()
{
    int n;
    cin >> n;
    vector<long long> num(n), n_sum(n + 1);
    for (auto& a : num)
    {
        cin >> a;
    }
    n_sum[0] = 0;
    for (int i = 0; i < n; i++)
        n_sum[i + 1] = n_sum[i] + num[i];
    int m, a, b;
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b;
        cout << n_sum[b + 1] - n_sum[a] << endl;
    }
}
void Bins_ex()
{
    int n;
    cin >> n;
    vector<long long> num(n);
    for (auto& a : num)
    {
        cin >> a;
    }
    int m;
    long long a;
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> a;
        int l = 0, r = n - 1;
        while (l < r)
        {
            int m = (l + r + 1) / 2;
            if (num[m] <= a)
            {
                l = m;
            }
            else
            {
                r = m - 1;
            }
        }
        cout << l << endl;
    }
}

vector<long long> cows;

int checkCows(int a)
{
    vector<int> ans_arr(cows.size());
    ans_arr[0] = 1;
    int ans = 1;
    for (int i = 1; i < cows.size(); i++)
    {
        int ind = upper_bound(cows.begin(), cows.end(), cows[i] - a) - cows.begin() - 1;
        if (ind < 0)
            ans_arr[i] = 1;
        else
            ans_arr[i] = ans_arr[ind] + 1;
        ans = max(ans_arr[i], ans);
    }
    return ans;
}
void Cows()
{
    int n, sell;
    cin >> n >> sell;
    cows.resize(n);
    for (auto& a : cows)
        cin >> a;
    sort(cows.begin(), cows.end());
    int l = 0, r = cows.back();
    while (l < r)
    {
        int m = (l + r + 1) / 2;
        if (n - checkCows(m) <= sell)
            l = m;
        else
            r = m - 1;
    }
    cout << l << endl;
}

void Ternary()
{
    double l = -PI / 2, r = PI / 2;
    while (r - l > 0.001)
    {
        double m1 = (l * 2 + r) / 3, m2 = (l + r * 2) / 3;
        if (cos(m1) > cos(m2))
            r = m2;
        else
            l = m1;
    }
    cout << l << endl;
}

void SubseqNN()
{
    int n;
    cin >> n;
    vector<long long> nums(n);
    vector<vector<long long>> subseq(n);
    vector<int> ans(n);
    for (auto& a : nums)
        cin >> a;
    subseq[0] = { nums[0],INT64_MAX };
    ans[0] = 1;
    int max_ans = 1, maxi = 0;
    for (int i = 1; i < nums.size(); i++)
    {
        subseq[i] = subseq[i - 1];
        int ind = upper_bound(subseq[i].begin(), subseq[i].end(), nums[i]) - subseq[i].begin();
        subseq[i][ind] = nums[i];
        ans[i] = ind + 1;
        if (ans[i] > max_ans)
        {
            max_ans = ans[i];
            maxi = i;
        }
        if (ind >= subseq[i].size() - 1)
            subseq[i].push_back(INT64_MAX);
    }
    cout << max_ans << endl;
    subseq[maxi].pop_back();
    for (auto& a : subseq[maxi])
        cout << a << " ";
    cout << endl;
}

void SubseqNlogN()
{
    int n;
    cin >> n;
    vector<long long> nums(n);
    vector<long long> subseq;
    for (auto& a : nums)
        cin >> a;
    subseq = { nums[0],INT64_MAX };
    int max_ans = 1, maxi = 0;
    for (int i = 1; i < nums.size(); i++)
    {
        int ind = upper_bound(subseq.begin(), subseq.end(), nums[i]) - subseq.begin();
        subseq[ind] = nums[i];
        if (ind + 1 > max_ans)
        {
            max_ans = ind + 1;
            maxi = i;
        }
        if (ind >= subseq.size() - 1)
            subseq.push_back(INT64_MAX);
    }
    cout << max_ans << endl;
    subseq = { nums[0],INT64_MAX };
    for (int i = 1; i <= maxi; i++)
    {
        int ind = upper_bound(subseq.begin(), subseq.end(), nums[i]) - subseq.begin();
        subseq[ind] = nums[i];
        if (ind + 1 > max_ans)
        {
            max_ans = ind + 1;
            maxi = i;
        }
        if (ind >= subseq.size() - 1)
            subseq.push_back(INT64_MAX);
    }
    subseq.pop_back();
    for (auto& a : subseq)
        cout << a << " ";
    cout << endl;
}

void MapAlt()
{
    vector<long long> keys, nums;
    keys = { 1,3,1000000,99999999 };
    nums = { 0,0,0,0 };
    long long key = 99999999;
    int ind = lower_bound(keys.begin(), keys.end(), key) - keys.begin();
    nums[ind]++;
    cout << nums[ind] << endl;
}

int main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    return 0;
}