Cod sursa(job #1456282)

Utilizator NistorSergiuNistor Sergiu NistorSergiu Data 30 iunie 2015 11:50:25
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <fstream>
#include <deque>

using namespace std;

deque <pair <int, int> > d;

void insertInDeque(int value, int position)
{
    if(d.empty())
    {
        d.push_back(make_pair(value, position));
        return;
    }
    int left = -1;
    int right = d.size();
    int mid;
    while(left + 1 < right)
    {
        mid = (left + right) / 2;
        if(value < d[mid].first)
            right = mid;
        else
            left = mid;
    }
    d.insert(d.begin() + left + 1, make_pair(value, position));
    d.erase(d.begin() + left + 2, d.end());
}

/*void insertInDeque(int value, int position)
{
    if(d.empty())
    {
        d.push_back(make_pair(value, position));
        return;
    }
    int left = 0;
    int right = d.size() - 1;
    int mid;
    while(left + 1 < right)
    {
        mid = (left + right) / 2;
        if(value <= d[mid].first)
            right = mid;
        else
            left = mid + 1;
    }
    d.insert(d.begin() + right, make_pair(value, position));
    d.erase(d.begin() + right + 1, d.end());
}*/

int getFromDeque(int left)
{
    deque <pair <int, int> > :: iterator it;
    for(it = d.begin(); it != d.end(); it++)
        if(it->second >= left)
            break;
    d.erase(d.begin(), it);
    return it->first;
}

int main()
{
    int n, k;
    int left, right;
    int bestL, bestR, bestB;
    int value;
    ifstream f("secventa.in");
    f >> n >> k;
    for(right = 1; right <= k; right++)
    {
        f >> value;
        insertInDeque(value, right);
    }
    bestL = 1; bestR = k; bestB = getFromDeque(1);
    for(left = 2; right <= n; left++, right++)
    {
        f >> value;
        insertInDeque(value, right);
        value = getFromDeque(left);
        if(value > bestB)
        {
            bestB = value;
            bestL = left;
            bestR = right;
        }
    }
    ofstream g("secventa.out");
    g << bestL << " " << bestR << " " << bestB << "\n";
    g.close();
    return 0;
}