# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
119719208 |
Practice:
frank152 |
939F
- 31
|
GNU C++11
|
Accepted
|
31 ms
|
2356 KB
|
2021-06-17 17:02:03 |
2021-06-17 17:02:03 |
|
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=1e5+5,inf=1e6;
int h,t,q[maxn<<1];
int n,k,l,r,f[2][maxn<<1];
int main(){
memset(f[0],inf,sizeof(f));
f[0][0]=0;
scanf("%d%d",&n,&k);
for(int i=1;i<=k;++i){
scanf("%d%d",&l,&r);
for(int j=0;j<=n;++j)
f[i&1][j]=f[!(i&1)][j];
h=1,t=0;
for(int j=r;~j;--j){
while(h<=t&&q[h]<l-j)
++h;
while(h<=t&&f[!(i&1)][q[t]]>f[!(i&1)][r-j])
--t;
q[++t]=r-j;
f[i&1][j]=min(f[i&1][j],f[!(i&1)][q[h]]+1);
}
h=1,t=0;
for(int j=0,MAX=min(n,r);j<=MAX;++j){
while(h<=t&&q[h]<j-r+l)
++h;
while(h<=t&&f[!(i&1)][q[t]]>f[!(i&1)][j])
--t;
q[++t]=j;
f[i&1][j]=min(f[i&1][j],f[!(i&1)][q[h]]+2);
}
}
if(f[k&1][n]>inf)
puts("Hungry");
else
printf("Full\n%d\n",f[k&1][n]);
}
Click to see test details