Cod sursa(job #2047515)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 24 octombrie 2017 22:14:07
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <bits/stdc++.h>
#define Nmax 100001
using namespace std;

int n,x,y,st,dr;
double v[Nmax];
pair<double,bool> P[Nmax],rez;
deque<tuple<double,bool,int> > Q;

int sgn(pair<double,bool> a,pair<double,bool> b)
{
    if (a.second==1 && b.second==0)
        return -1;
    if (a.second==0 && b.second==1)
        return 1;
    if (a.second==0)
    {
        if (a.first<b.first)
            return -1;
        else if (a.first==b.first)
            return 0;
        return 1;
    }

    if (a.first<b.first)
        return 1;
    else if (a.first==b.first)
        return 0;
    return -1;
}

int main()
{
    freopen("secv4.in","r",stdin);
    freopen("secv4.out","w",stdout);

    cin>>n>>x>>y;
    for (int i=1;i<=n;i++)
    {
        scanf("%f",&v[i]);
        P[i] = P[i-1];
        if (v[i]<0)
        {
            P[i].second ^= 1;
            P[i].first += log10(v[i]);
        }
    }
    for (int i=1;i<=n/2;i++)
        swap(P[i],P[n-i+1]);

    int dif = y-x;
    for (int i=1;i<=n-x;i++)
    {
        while (!Q.empty() && sgn({get<0>(Q.back()),get<1>(Q.back())},P[i])<=0)
            Q.pop_back();
        Q.push_back(make_tuple(P[i].first,P[i].second,i));
        if (get<2>(Q.front()) <= i-dif)
            Q.pop_front();
        if (sgn(rez,{get<0>(Q.front()),get<1>(Q.front())})<=0)
        {
            rez = {get<0>(Q.front()),get<1>(Q.front())};
            st = n-(i+x)+1;
            dr = n-get<2>(Q.front())+1;
        }
    }

    cout<<dr-st+1<<' '<<st;
    return 0;
}