Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
28195 | LYLAKIOI | 【BJ】T3 | C++ | 运行超时 | 67 | 3030 MS | 15872 KB | 1367 | 2024-04-05 08:30:13 |
#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; }