Пещера с монстрами

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 22e4;
 
int a[N], t[N];
int cal(int n) {
    int ans = 1;
    for (int i = 0, l = -1, mx = 0; i < n; i++) {
        mx = max(mx, a[i]);
        if (t[i - l] < mx)l = i - 1, ans++, mx = a[i];
        if (t[1] < a[i])return -1;
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(0);
    int T=1, n, m;
    
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            t[i + 1] = 0;
        }
        cin >> m;
        for (int i = 0, x, y; i < m; i++) {
            cin >> x >> y;
            t[y] = max(t[y], x);
        }
        for (int i = n - 1; i > 0; i--) {
            t[i] = max(t[i], t[i + 1]);
        }
        cout << cal(n) << '\n';
    }
    return 0;
}

#include <iostream>
#include <cmath>
using namespace std;
long maxim(long a[], long n){
    long max=0;
    for (long y=0; y<n; y++){
        if (a[y]>max){max=a[y];}
    }
    return max;
}
int main()
{
    long n, m;
    cin>>n;
    long h[n];
    for (long y=0; y<n; y++){
        cin>>h[y];
    }
    cin>>m;
    if (m<n){cout<<-1;}
    else{
        long l=0;
        long r=maxim(h, n);
        //cout<<r<<endl;
       // if (m==n){cout<<r;}
 
        while (r-l>1){
            long d=(r+l)/2;
            long b=0;
            for (long y=0; y<n; y++){
                    b+=h[y]/d;
                    if (h[y]%d!=0){b++;}
            }
            if (b>=m){l=d;}
            else {r=d;}
        }
        cout<<r;
 
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <cctype>
#include <algorithm>
#include <iterator>
 
using namespace std;
 
#define ll long long
 
bool OK(vector<ll>h, int L, int n, int m) {
    ll res = 0;
    for (int i = 0; i < n; i++) {
        res += (h[i] + L - 1) / L;
    }
    return (res <= m) ? true : false;
}
 
int main() {
    int n;
    cin >> n;
    vector<ll> h(n);
    vector<ll> ::iterator it;
    for (int i = 0; i < h.size(); ++i) {
        cin >> h[i];
    }
    int m;
    cin >> m;
    if (m < n) {
        cout << -1;
    }
    else {
        ll l = 0;
        it = max_element(h.begin(), h.end());
        ll r = *it;
        while (r-l>1) {
            int L = (r + l) / 2;
            (OK(h, L, n, m)) ? r = L: l = L;
        }
        cout << r;
    }
}

int foo(std::vector<int> &h, int m)
{
    if(h.size() > m) return -1;
 
    std::sort(h.rbegin(), h.rend());
 
    auto check = [&h](int x, int m)
    {
        int mlt = h.front() / x + (h.front() % x > 0);
        int pwr = (mlt - 1) * x;
 
        auto left = h.begin();
        while(left != h.end())
        {
            auto right = std::find_if(left, h.end(), [&pwr](auto a){ return a <= pwr; });
            m -= std::distance(left, right) * mlt;
 
            if(m < 0) return false;             //
            if(right == h.end()) return true;   //
 
            while(*right <= pwr)
            {
                --mlt;
                pwr -= x;
            }
            left = right;
        }
        return m >= 0;
    };
    
    int result = h.front();
    int l = 0;
    int r = h.front() + 1;
    
    while(r - l > 1)
    {
        int x = (l + r) / 2;
        if(check(x, m))
        {
            result = x;
            r = x;
        } else {
            l = x;
        }
    }
    
    
    return result;
}

#include<iostream>
 
using namespace std;
 
 
 
bool read_input_as_correct( int &x, int Min, int Max )
 {
cin >> x;
 
if( x < Min || x > Max )
 {
 cout << "Incorrect user input. Enter again: ";
 read_input_as_correct( x, Min, Max );
 }
return true;
 }
 
long long magic_quantity( int n, int *h, int supposed_X )
 {
long long mq = 0;
int remainder = 0;
 
for( int i=0; i<n; i++ )
 {
 
 if( supposed_X >= h[ i ] )
  {
  mq += supposed_X;
  }
 else
  {
  mq += h[ i ];
  remainder = h[ i ] % supposed_X;
  if( remainder ) mq += ( supposed_X - remainder );
  }
 }
return mq;
 }
 
 
 
 
 
int main()
 {
int NO_MONSTERS = 2; // Namber Of Mansters
int heros_stamina = 0; // Hero`s stamina
int i, flag=-1;
long long Z=0;
int *monster_health;
 
 
// GET USER INPUT
cout << "\n --Enter data--\n";
 
cout << "1. Namber of mansters\n   (you can enter a number between 1 and 100000): ";
read_input_as_correct( NO_MONSTERS, 1, 100000 );
monster_health = new int[ NO_MONSTERS ];
if( !monster_health ) return 1;
 
cout << "2. The health of each monster\n   (you can enter a number between 1 and 1000000):\n";
 
for( i=0; i<NO_MONSTERS; i++ )
 {
 cout << "Monster numer " << i+1 << " health: ";
 read_input_as_correct( monster_health[ i ], 1, 1000000 );
 
//cout << "-----  " << monster_health[ i ] << " ----";
//getch();
 }
 
cout << "3. Hero`s stamina\n   (you can enter a number between 1 and 1000000): ";
read_input_as_correct( heros_stamina, 1, 1000000 );
// - - - - - - - -
 
 
for( int c=1; c<=heros_stamina; c++ )
 {
 Z = magic_quantity( NO_MONSTERS, monster_health, c );
 if( heros_stamina - Z/c >= 0 )
  {
  flag = c;
  break;
  }
 }
 
cout << flag << endl;
 
delete monster_health;
return 0;
 }

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool f(vector<int> h, int x, int n, int m)
{
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += (h[i] + x - 1) / x;
    }
    return ans <= m;
}
 
int main()
{
    int n, m, temp;
    cin >> n;
    vector<int> h;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        h.push_back(temp);
    }
    cin >> m;
    if (n <= m) {
        int l = 0, r = *max_element(h.begin(), h.end());
        while (r > l + 1) {
            int x = (r + l) / 2;
            if (f(h, x, n, m)) r = x;
            else l = x;
        }
        cout << r;
    }
}