Cod sursa(job #1604198)

Utilizator aimrdlAndrei mrdl aimrdl Data 18 februarie 2016 00:56:22
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <iostream>
#include <deque>
 
using namespace std;
 
struct item {
    int val;
    int pos;
};
 
int main (void) {     
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);
     
    char *in = (char *) malloc(1024 * 1024 * 10 * sizeof(char));
    fgets(in, 1024 * 1024 * 10, stdin);
    
    int n = 0, k = 0;
    int idx;
    for(; in[idx] >= '0' && in[idx] <= '9'; ++idx) {
    	 n += n * 10 + in[idx] - '0';
    }
    while (in[idx] < '0' || in[idx] > '9') ++idx;
    for(; in[idx] >= '0' && in[idx] <= '9'; ++idx) {
    	 k += k * 10 + in[idx] - '0';
    }
    int v[500005] = {0};
    fgets(in, 1024 * 1024 * 7, stdin);
    idx = 0;
    for (int i = 0; i < n; ++i) {
    	int sign = 1;
    	if (in[idx] == '-') {
    		sign = -1;
    		++idx;
    	}
    	
    	while (in[idx] >= '0' && in[idx] <= '9') {
    		v[i] += v[i] * 10 + in[idx] - '0';
    		++idx;
    	}
    	v[i] *= sign;
    
    	while ((in[idx] < '0' || in[idx] > '9') && in[idx] != '-') ++idx; 
    }
     
    deque<item> l;
     
    item aux;
    int max = 0, endSol = 0;
     
    for (int i = 0; i < k; ++i) {
        while (!l.empty() && v[i] <= l.back().val) {
            l.pop_back();
        }
         
        aux.val = v[i];
        aux.pos = i;
        l.push_back(aux);
    }
         
         
    max = l.front().val;
    endSol = l.front().pos;
     
    for (int i = k; i < n; ++i) {    
        while (!l.empty() && v[i] <= l.back().val) {
            l.pop_back();
        }
         
        aux.val = v[i];
        aux.pos = i;
        l.push_back(aux);
         
        if (l.front().pos <= i - k) l.pop_front();
         
        if (l.front().val > max) {
            max = l.front().val;
            endSol = i;
        }
    }
     
    cout << endSol - k  + 2 << " " << endSol + 1 << " " << max;
    free(in);
    return 0;
}