Cod sursa(job #2617689)

Utilizator PopescuAndreiAlexandruPopescu Andrei Alexandru PopescuAndreiAlexandru Data 22 mai 2020 17:04:31
Problema Secventa 2 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

ifstream fin("secv2.in");
ofstream fout("secv2.out");

const long long INF = (1<<63);
const int DIM = 50005;

long long n,k,S,x,ans,pos,Max=ans,stx,sty;

struct SegmentTree
{
    long long val,pos;
}Tree[DIM*4+5];

void UpdateTree(int nod, int st, int dr, int pos, long long val)
{
    if(st==dr)
    {
        Tree[nod].val=val;
        Tree[nod].pos=pos;
        return;
    }
    int mij=(st+dr)/2;
    if(pos<=mij)
        UpdateTree(2*nod,st,mij,pos,val);
    else
        UpdateTree(2*nod+1,mij+1,dr,pos,val);
    if(Tree[2*nod].val<Tree[2*nod+1].val)
    {
        Tree[nod].val=Tree[2*nod].val;
        Tree[nod].pos=Tree[2*nod].pos;
    }
    else
    {
        Tree[nod].val=Tree[2*nod+1].val;
        Tree[nod].pos=Tree[2*nod+1].pos;
    }
}

void QueryTree(int nod, int st, int dr, int a, int b)
{
    if(st>=a && dr<=b)
    {
        if(Tree[nod].val<ans)
        {
            ans=Tree[nod].val;
            pos=Tree[nod].pos;
        }
        return;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
        QueryTree(2*nod,st,mij,a,b);
    if(b>mij)
        QueryTree(2*nod+1,mij+1,dr,a,b);
}

int main()
{
    fin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        fin>>x;
        S+=x;
        int a=1;
        int b=i-k;
        ans=INF;
        if(a<=b)
            QueryTree(1,1,n,a,b);
        int p=S-ans;
        if(p>Max)
        {
            Max=p;
            stx=pos+1;
            sty=i;
        }
        UpdateTree(1,1,n,i,S);
    }
    fout<<stx<<" "<<sty<<" "<<Max<<'\n';
}