# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
100190975 |
Practice:
crazyZTW |
939F
- 31
|
GNU C++11
|
Accepted
|
46 ms
|
2360 KB
|
2020-12-02 16:06:05 |
2020-12-02 16:06:05 |
|
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10, inf = 0x3f3f3f3f;
int n, m, f[2][N], q[N];
signed main() {
cin >> n >> m;
int o = 1; memset(f, 0x3f, sizeof(f)); f[0][0] = 0;
while(m--) {
int L, R; cin >> L >> R;
int l, r; q[l=r=1] = 0;
for(int i = 0; i <= min(R, n); i++) {
while(l <= r && f[!o][q[r]] >= f[!o][i]) r--;
q[++r] = i;
while(l < r && q[l] < i - (R-L)) l++;
f[o][i] = min(f[!o][i], f[!o][q[l]] + 2);
}
q[l=r=1] = 0;
for(int i = R; i >= 0; i--) {
while(l <= r && f[!o][q[r]] >= f[!o][R-i]) r--;
q[++r] = R - i;
while(l < r && q[l] < L - i) l++;
f[o][i] = min(f[o][i], f[!o][q[l]] + 1);
}
o ^= 1;
}
if(f[!o][n] == inf) puts("Hungry");
else printf("Full\n%d\n", f[!o][n]);
}
Click to see test details