Районная олимпиада по информатике. 2018-2019 учебный год. 8-11 классы

Есеп H. Өспелі бөліктер

Ограничение по времени:

1 second

Ограничение по памяти:

256 megabytes

Сізде ұзындығы $n$ $a$ массивы бар. Берілген массивке байланысты сізге $q$ рет сұрақ қойылады. Сұрақтардың бәрінің үлгісі бірдей, тек сандары өзгереді. Әр сұрақта сізге белгілі бір аралықты анықтайтын $l$ және $r$ берілген. Осы аралықты ($a_l, a_{l+1}, \ldots, a_r$) $k$ бөлікке бөліңіз. Бірақ, әр бөлігін жеке алып қараған кезде тек өспелі массив шығу керек. $k$-ның мәнін барынша кішірейтіңіз.

Формат входного файла

Бірінші жолда екі сан берілген $n, q$ - массивтін ұзындығы және сұраулар саны. Екінші жолда $n$ сан берілген - а массиві. Әр келесі $q$ жолда екі сан берілген, $l$ және $r$.

Формат выходного файла

Әр сұрақта берілген аралықты ережеге сәйкес $k$ рет бөліңіз және $k$-ның мәнін шығарыңыз.

Пример:

Вход

4 3
3 1 4 2
1 4
1 3
4 4

Ответ

3
2
1

Замечание

Егер барлық $l \leq i \leq r - 1$ үшін $a_i < a_{i+1}$ болса, $a_l, a_{l+1}, \ldots, a_r$ массив бөлігі өспелі деп аталады. Бірінші мысалдағы сұрауларға жауаптар: $\\ $ [3, 1, 4, 2] - [3], [1, 4], [2] $\\ $ [3, 1, 4] - [3], [1, 4] $\\ $ [4] - [4] $\\ $ $1 \leq n, q \leq 1000$ - 40 ұпай. $\\ $ $1 \leq n, q \leq 10^5$ - 60 ұпай. $\\ $ ( Nurlybek Aimagambetov )

Комментарий/решение

AC

кодты корсету/жасыру

#include<iostream>
#include<algorithm>
#include<cmath>
#define ll long long int
using namespace std;
int main(){
	ll n,q,a[101000],dp[101000],k=1,l,r;
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
		if(a[i-1]>=a[i])k++;
		dp[i]=k;
	}
	while(q--){
		cin>>l>>r;
		cout<<dp[r]-dp[l]+1<<"\n";
	}
}

C++

Copy

кодты корсету/жасыру

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
    int n,q;
    cin >> n >> q;
    int a[n+1];
    a[0]=1e6;
    for (int i=1; i<=n; i++) cin >> a[i];

    int b[n+1];
    b[0]=0;
    for (int i=1; i<=n; i++) {
        b[i] = b[i-1];
        if (a[i]<=a[i-1]) b[i]++;
    }

    for (int i=1; i<=q; i++) {
        int l,r;
        cin >> l >> r;
        cout << b[r] - b[l] + 1 << '\n';
    }
    return 0;
}

C++

Copy

кодты корсету/жасыру

#include <iostream>
#include<algorithm>
using namespace std;

int main()
{
   ios::sync_with_stdio(false);
   int n, q;
   cin >> n >> q;
   int a[n], D[n];
   for(int i=0; i<n; i++){
       cin >> a[i];
   }
   D[0] = 1;
   for(int i = 1; i<n; i++){
   D[i] = D[i-1];
       if(a[i] <= a[i-1]){
           D[i] += 1;
       }
   }

   for(int i=0; i<q; i++){
       int l, r;
       cin >> l >> r;
       cout << D[r-1] - D[l-1] + 1 << endl;
   }

    return 0;
}

C++

Copy