În practică, programul poate arăta în felul următor:
== code(cpp) |
// ...
#include <fstream>
#include <deque>
#include <algorithm>
using namespace std;
deque <int> min_deq, max_deq;
#define MAXN 100005
typedef int (*PF)(const int , const int ) ;
int V[MAXN];
deque <int> min_deq, max_deq;
int min_fct(const int a, const int b) { return a < b; }
int max_fct(const int a, const int b) { return a > b; }
void push_in(deque <int>& deq, const int p, PF compare) {
for (; !deq.empty() && compare(S[p], S[deq.back()]); deq.pop_back()) ;
for (; !deq.empty() && compare(V[p], V[deq.back()]); deq.pop_back()) ;
deq.push_back(p);
}
int query(deque <int>& deq, const int j) {
for (; !deq.empty() && deq.front() <= j; deq.pop_front()) ;
return S[deq.front()];
return V[deq.front()];
}
int main(void) {
// ...
for (int i = 1; i <= N; ++ i) {
int main(void)
{
ifstream in("sir.in"); ofstream out("sir.out");
int n, X, Y, Z;
int length = 0, start, stop, j = 0;
in >> n >> X >> Y >> Z;
for (int i = 1; i <= n; ++ i) {
in >> V[i];
push_in(min_deq, i, min_fct);
push_in(max_deq, i, max_fct);
while ((j < i - Y || query(max_deq, j) - query(min_deq, j) > Z) && j < i - X)
j ++;
// (j, i] este intervalul candidat la soluţia pentru pozitia i
if (j <= i - X) if (query(max_deq, j) - query(min_deq, j) <= Z)
// compară cu rezultatul de până acum
if (i - j >= length)
length = i - j, start = j + 1, stop = i;
}
// ...
length > 0 ? out << length << " " << start << " " << stop : out << -1;
in.close(), out.close();
return 0;
}
==