Cod sursa(job #3291237)

Utilizator TeodorVTeodorV TeodorV Data 3 aprilie 2025 19:34:59
Problema Plantatie Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <bits/stdc++.h>

using namespace std;

const string NUMEFISIER="diagonala";
ifstream fin(NUMEFISIER+".in");
ofstream fout(NUMEFISIER+".out");

int main()
{
    int n;
    fin>>n;
    deque<int> dq_st,dq_dr;
    vector<int> st(n),dr(n);

    int j=0,lmax=0;
    for(int i=0; i<n; i++)
    {
        fin>>st[i]>>dr[i];
        st[i]-=i;
        dr[i]-=i;
        while(!dq_st.empty() && st[i]>=st[dq_st.back()])
            dq_st.pop_back();
        dq_st.push_back(i);
        while(!dq_dr.empty() && dr[i]<=dr[dq_dr.back()])
            dq_dr.pop_back();
        dq_dr.push_back(i);

        while(st[dq_st.front()]>dr[dq_dr.front()] && j<=i)
        {
            if(dq_st.front()==j)
                dq_st.pop_front();
            if(dq_dr.front()==j)
                dq_dr.pop_front();

            j++;
        }
        lmax=max(lmax, i-j+1);
    }
    dq_st.clear(); dq_dr.clear();

    j=0;
    for(int i=0; i<n; i++)
    {
        st[i]+=2*i;
        dr[i]+=2*i;
        while(!dq_st.empty() && st[i]>=st[dq_st.back()])
            dq_st.pop_back();
        dq_st.push_back(i);
        while(!dq_dr.empty() && dr[i]<=dr[dq_dr.back()])
            dq_dr.pop_back();
        dq_dr.push_back(i);

        while(st[dq_st.front()]>dr[dq_dr.front()] && j<=i)
        {
            if(dq_st.front()==j)
                dq_st.pop_front();
            if(dq_dr.front()==j)
                dq_dr.pop_front();

            j++;
        }
        lmax=max(lmax, i-j+1);
    }
    fout<<lmax;
    return 0;
}