Kvar_ispw17's blog
0%

Posted on In

Codeforces gym 101611H. Hilarious Cooking 题解

题解

把问题转化为寻找可行的范围 \([L,R]\)，判断是否 \(T\in [L,R]\)，由于题目中的限制，可以得到所有关键点之间的中间最大和最小状态，可以直接计算“面积”，从左到右依次计算即可得到 \(L, R\).

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// https://codeforces.com/gym/101611/problem/H
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;
typedef long long ll;
 
template <typename _Tp>
void read(_Tp &a, char c = 0, int f = 1) {
    for(c = getchar(); !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar()); a *= f;
}
 
template <typename _Tp>
void write(_Tp a) {
    if(a < 0) putchar('-'), a = -a;
    if(a > 9) write(a / 10); putchar(a % 10 + '0');
}

const int N = 2e9 + 5;
const int M = 1e5 + 5;

ll T, n, m, L, R;
ll a[M], b[M];

#define ZERO 0ll

ll f(ll x, ll y) { return (abs(y - x) + 1) * (x + y) / 2; }

ll getMIN(ll x1, ll y1, ll x2, ll y2) { 
    ll dy = abs(y1 - y2);
    ll dx = abs(x1 - x2);
    if(dx < dy) return -1;
    ll p = (y1 - y2 + x1 + x2) / 2;
    ll py1 = y1 - (p - x1);
    ll py2 = y2 - (x2 - p);
    if(py1 == py2)
        if(py1 < 0) return f(y1, 0) + f(0, y2);
        else return f(y1, py1) + f(py1, y2) - py1;
    else
        if(py1 < 0) return f(y1, 0) + f(0, y2);
        else return f(y1, py1) + f(py1, y2);
}

ll getMAX(ll x1, ll y1, ll x2, ll y2) {
     ll dy = abs(y1 - y2);
    ll dx = abs(x1 - x2);
    if(dx < dy) return -1;
    ll p = (y2 - y1 + x1 + x2) / 2;
    ll py1 = y1 + (p - x1);
    ll py2 = y2 + (x2 - p);
    if(py1 == py2) return f(y1, py1) + f(py1, y2) - py1;
    else return f(y1, py1) + f(py1, y2);
}

int main() {
    // freopen("0801_2.in", "r", stdin);
    read(T), read(n), read(m);
    for(int i = 1; i <= m; i++) {
        read(a[i]);
        read(b[i]);
    }
    L += f(max(ZERO, b[1] - (a[1] - 1)), b[1]) - b[1];
    R += f(b[1], b[1] + (a[1] - 1)) - b[1];  // for [x1,x2)
    bool _ = 1;
    // printf("L = %lld  R = %lld\n", L, R);
    for(int i = 1; i <= m - 1; i++) {
        ll tMIN = getMIN(a[i], b[i], a[i + 1], b[i + 1]);
        ll tMAX = getMAX(a[i], b[i], a[i + 1], b[i + 1]);
        if(tMIN == -1 || tMAX == -1) {
            _ = 0;
            break;
        }
        L += tMIN - b[i + 1]; // for [x1,x2)
        R += tMAX - b[i + 1];
        // printf("L = %lld  R = %lld\n", L, R);
    }
    if(!_) {
        puts("No");
        return 0;
    }
    L += f(max(ZERO, b[m] - (n - a[m])), b[m]);
    R += f(b[m], b[m] + (n - a[m]));
    // printf("L = %lld  R = %lld\n", L, R);
    if(L <= T && T <= R) puts("Yes");
    else puts("No");
    return 0;
}