提交时间:2024-04-05 08:30:13

运行 ID: 28195

#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=1e6+5,mod=1e9+7; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')t=-1;ch=getchar(); }while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,a[maxn],b[maxn],dp1[maxn],dp2[maxn]; void slv(){ n=read();up(i,1,n)a[i]=read(),b[i]=read(); memset(dp1,128,sizeof(dp1)); dp1[0]=0,dp2[0]=1; up(i,1,n){ int mx=-1e9,mn=1e9; int res1=-1e9,res2=0; down(j,i,1){ mx=max(mx,a[j]),mn=min(mn,b[j]); if(mx>mn||i-j+1>mn||i<mx)break; if(i-j+1>=mx&&i-j+1<=mn){ int ret=dp1[j-1]+1; if(ret>res1)res1=ret,res2=dp2[j-1]; else if(ret==res1)(res2+=dp2[j-1])%=mod; } } dp1[i]=res1,dp2[i]=res2; } if(dp1[n]>0)printf("%d %d\n",dp1[n],dp2[n]); else printf("-1\n"); }int main(){ // freopen("schooldays.in","r",stdin); // freopen("schooldays.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }