# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
118868122 |
Practice:
CHK666 |
939F
- 31
|
GNU C++11
|
Accepted
|
46 ms
|
2360 KB
|
2021-06-09 11:52:18 |
2021-06-09 11:52:18 |
|
#include<bits/stdc++.h>
using namespace std;
#define N 100005
int head,tail,que[N<<1],n,k,l,r,f[2][N<<1];
int main(){
memset(f[0],0x3f,sizeof f[0]);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];
head=1;tail=0;
for(int j=r;j>=0;j--){
while(head<=tail&&que[head]<l-j)head++;
while(head<=tail&&f[!(i&1)][que[tail]]>f[!(i&1)][r-j])tail--;
que[++tail]=r-j;
f[i&1][j]=min(f[i&1][j],f[!(i&1)][que[head]]+1);
}
head=1;tail=0;
for(int j=0;j<=min(n,r);j++){
while(head<=tail&&que[head]<j-r+l)head++;
while(head<=tail&&f[!(i&1)][que[tail]]>f[!(i&1)][j])tail--;
que[++tail]=j;
f[i&1][j]=min(f[i&1][j],f[!(i&1)][que[head]]+2);
}
}
// for(int i=0;i<=n;i++)cout<<f[!][n]<<endl;
if(f[k&1][n]>1e9)puts("Hungry");
else printf("Full\n%d",f[k&1][n]);
}
Click to see test details