Pagini recente » Cod sursa (job #3209119) | Cod sursa (job #17197) | Cod sursa (job #113575) | Cod sursa (job #30644) | Cod sursa (job #3291237)
#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;
}