Cod sursa(job #778840)

Utilizator adascaluAlexandru Dascalu adascalu Data 15 august 2012 23:08:40
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<fstream>

#include<deque>

 

using namespace std;

deque < pair <int, int> > A;

#define MAXN 500002

int v[ MAXN ], n, k, x, y, res = -MAXN;

void solve()

{

ifstream f("secventa.in");

int i;

f >> n >> k;

for(i = 1; i < k; i++)

{

f >> v[i];

 

while(!A.empty() && v[i] <= A.back().second)

A.pop_back();

A.push_back(make_pair(i, v[i]));

if(i - k == A.front().first)

A.pop_front();

}

 

for( ; i <= n; i++)         

{

f >> v[i];

while(!A.empty() && v[i] <= A.back().second)

A.pop_back();

A.push_back(make_pair(i, v[i]));

if(i - k == A.front().first)

A.pop_front();

if(A.front().second > res)

res = A.front().second, y = i;

}

 

f.close();

x = y - k + 1;

}

void write()

{

ofstream g("secventa.out");

 

g << x << " " << y << " " << res << '\n';

 

g.close();

}

 

int main()

{

solve();

write();

return 0;

}