Cod sursa(job #1862676)

Utilizator NinjaCubeMihai Radovici NinjaCube Data 30 ianuarie 2017 10:15:19
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <cstdio>
#include <deque>


using namespace std;
struct nod{
    int val, id;
    nod(int _v, int _i) {val = _v; id = _i;};
    nod(){};
};

int main() {
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);
    int N, K, i, j;
    deque<nod> Q;
    scanf("%d %d\n", &N, &K);
    char c[7];
    int sol = -32222, left;
    for (i=1; i<K; i++) {
        int X = 0;
        int neg = 1;
        scanf("%s", &c);

        int dd = 0;
        if (c[0] == '-') neg =-1, dd = 1;
        for (; c[dd]; dd++) {
            X*=10; X+=c[dd]-'0';
            }
        X*=neg;
        //printf("AM: %d\n", X);

        //X se duce la dreapta
        //scot din dreapta tot ce este mai mare ca X
        while (!Q.empty()) {
            nod A = Q.front();
            if (A.val >= X) Q.pop_front();
            else break;
        }
        Q.push_front(nod(X, i));
        //baga in dreapta X
        //scoate din stanga tot ce este mai batran de K pasi
        while (!Q.empty()) {
            nod A = Q.back();
            if (A.id < i - K + 1) Q.pop_back();
            else break;
            }

        }


for (i=K; i<=N; i++) {

        int X = 0;
        int neg = 1;
        scanf("%s", &c);
        int dd = 0;
        if (c[0] == '-') neg =-1, dd = 1;
        for (; c[dd]; dd++) {
            X*=10; X+=c[dd]-'0';
            }
        X*=neg;
        //printf("AM: %d\n", X);

        //X se duce la dreapta
        //scot din dreapta tot ce este mai mare ca X
        while (!Q.empty()) {
            nod A = Q.front();
            if (A.val >= X) Q.pop_front();
            else break;
        }
        Q.push_front(nod(X, i));
        //baga in dreapta X
        //scoate din stanga tot ce este mai batran de K pasi
        while (!Q.empty()) {
            nod A = Q.back();
            if (A.id < i - K + 1) Q.pop_back();
            else break;
            }

        nod A = Q.back();

        if (A.val > sol) {left = i - K +1; sol = A.val;}

        }
printf("%d %d %d\n", left, left+K-1, sol);
return 0;
}