# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
132297056 |
Practice:
Yahbim |
939F
- 31
|
C++14 (GCC 6-32)
|
Accepted
|
31 ms
|
2356 KB
|
2021-10-18 02:50:47 |
2021-10-18 02:50:47 |
|
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int read(){
int ret=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) ret=ret*10+ch-'0',ch=getchar();
return ret;
}
int n,k,f[2][N<<1],q[N<<1];
int main(){
n=read(),k=read();
memset(f[0],0x3f,sizeof(f[0])),f[0][0]=0;
for(int i=1;i<=k;++i){
int l=read(),r=read();
for(int j=0;j<=n;++j) f[i&1][j]=f[i&1^1][j];
int h=0,t=0;
for(int j=r;j>=0;--j){
while(h<t&&q[h]<l-j) ++h;
while(h<t&&f[i&1^1][q[t-1]]>f[i&1^1][r-j]) --t;
q[t++]=r-j,f[i&1][j]=min(f[i&1][j],f[i&1^1][q[h]]+1);
}
h=t=0;
for(int j=0;j<=min(n,r);++j){
while(h<t&&q[h]<j-r+l) ++h;
while(h<t&&f[i&1^1][q[t-1]]>f[i&1^1][j]) --t;
q[t++]=j,f[i&1][j]=min(f[i&1][j],f[i&1^1][q[h]]+2);
}
}
if(f[k&1][n]==0x3f3f3f3f) printf("Hungry\n");
else printf("Full\n%d\n",f[k&1][n]);
return 0;
}
Click to see test details