{"id":158,"date":"2019-02-27T00:00:45","date_gmt":"2019-02-26T16:00:45","guid":{"rendered":"http:\/\/wwwwodddd.com\/?p=158"},"modified":"2019-04-17T13:44:46","modified_gmt":"2019-04-17T05:44:46","slug":"usaco-2019-feb","status":"publish","type":"post","link":"https:\/\/wwwwodddd.com\/wordpress\/usaco-2019-feb\/","title":{"rendered":"USACO 2019 FEB"},"content":{"rendered":"

<\/p>\n

Bronze<\/h1>\n

B1<\/h2>\n
import sys\nsys.stdin = open('herding.in', 'r')\nsys.stdout = open('herding.out', 'w')\nx, y, z = sorted(map(int, raw_input().split()))\nz -= y + 1\ny -= x + 1\nif y == 0 and z == 0:\n    print 0\nelif y == 1 or z == 1:\n    print 1\nelse:\n    print 2\nprint max(y, z)\n<\/code><\/pre>\n
B2<\/h2>\n
import sys\nsys.stdin = open('revegetate.in', 'r')\nsys.stdout = open('revegetate.out', 'w')\nn, m = map(int, raw_input().split())\na = [[] for i in range(n + 1)]\nfor i in range(m):\n    x, y = map(int, raw_input().split())\n    a[x].append(y)\n    a[y].append(x)\nc = [0 for i in range(n + 1)]\ns = ''\nfor i in range(1, n + 1):\n    t = set(range(1, 5))\n    for j in a[i]:\n        if j < i and c[j] in t:\n            t.remove(c[j])\n    c[i] = list(t)[0]\n    s += str(c[i])\nprint s\n<\/code><\/pre>\n
B3<\/h2>\n
import sys\nsys.stdin = open('traffic.in', 'r')\nsys.stdout = open('traffic.out', 'w')\nn = input()\na = []\nfor i in range(n):\n    x, y, z = raw_input().split()\n    y = int(y)\n    z = int(z)\n    a.append((x, y, z))\n\nl, h = 0, 1000000\nfor x, y, z in a[::-1]:\n    if x == 'none':\n        l = max(l, y)\n        h = min(h, z)\n    elif x == 'on':\n        l -= z\n        h -= y\n    elif x == 'off':\n        l += y\n        h += z\nl = max(l, 0)\nprint l, h\nl, h = 0, 1000000\nfor x, y, z in a:\n    if x == 'none':\n        l = max(l, y)\n        h = min(h, z)\n    elif x == 'on':\n        l += y\n        h += z\n    elif x == 'off':\n        l -= z\n        h -= y\nl = max(l, 0)\nprint l, h\n<\/code><\/pre>\n
Silver<\/h1>\n
S1<\/h2>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n, a[100020];\nint work() {\n    if (a[n - 1] == a[0] + n - 1) {\n        return 0;\n    }\n    if (a[n - 2] == a[0] + n - 2 || a[n - 1] == a[1] + n - 2) {\n        if (a[n - 1] == a[0] + n) {\n            return 1;\n        } else {\n            return 2;\n        }\n    }\n    int z1 = n;\n    for (int i = 0; i < n; i++) {\n        int p = a[i] + n - 1;\n        int t = upper_bound(a, a + n, p) - a;\n        z1 = min(z1, n - (t - i));\n    }\n    for (int i = 0; i < n; i++) {\n        int p = a[i] - n + 1;\n        int t = lower_bound(a, a + n, p) - a - 1;\n        z1 = min(z1, n - (i - t));\n    }\n    return z1;\n}\nint main() {\n    freopen(\"herding.in\", \"r\", stdin);\n    freopen(\"herding.out\", \"w\", stdout);\n    cin >> n;\n    for (int i = 0; i < n; i++) {\n        cin >> a[i];\n    }\n    sort(a, a + n);\n    int z2 = max(a[n - 1] - a[1], a[n - 2] - a[0]) - n + 2;\n    cout << work() << endl;\n    cout << z2 << endl;\n}\n<\/code><\/pre>\n
S2<\/h2>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n, k;\nint a[1020][1020];\nint main() {\n    freopen(\"paintbarn.in\", \"r\", stdin);\n    freopen(\"paintbarn.out\", \"w\", stdout);\n    cin >> n >> k;\n    for (int i = 0; i < n; i++) {\n        int x1, y1, x2, y2;\n        cin >> x1 >> y1 >> x2 >> y2;\n        x1++;\n        y1++;\n        x2++;\n        y2++;\n        a[x1][y1]++;\n        a[x1][y2]--;\n        a[x2][y1]--;\n        a[x2][y2]++;\n    }\n    for (int i = 1; i <= 1010; i++) {\n        for (int j = 1; j <= 1010; j++) {\n            a[i][j] += a[i][j - 1];\n        }\n    }\n    for (int i = 1; i <= 1010; i++) {\n        for (int j = 1; j <= 1010; j++) {\n            a[i][j] += a[i - 1][j];\n        }\n    }\n    int cnt = 0;\n    for (int i = 1; i <= 1010; i++) {\n        for (int j = 1; j <= 1010; j++) {\n            if (a[i][j] == k) {\n                cnt++;\n            }\n        }\n    }\n    cout << cnt << endl;\n    return 0;\n}\n<\/code><\/pre>\n
S3<\/h2>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n, m;\nint f[200020];\nint F(int x) {\n    return f[x] != x ? f[x] = F(f[x]) : x;\n}\nvoid U(int x, int y) {\n    f[F(x)] = F(y);\n}\nint main() {\n    freopen(\"revegetate.in\", \"r\", stdin);\n    freopen(\"revegetate.out\", \"w\", stdout);\n    cin >> n >> m;\n    for (int i = 0; i <= 2 * n; i++) {\n        f[i] = i;\n    }\n    for (int i = 0; i < m; i++) {\n        int x, y;\n        char o;\n        cin >> o >> x >> y;\n        if (o == 'S') {\n            U(x, y);\n            U(x + n, y + n);\n        } else {\n            U(x + n, y);\n            U(x, y + n);\n        }\n    }\n    for (int i = 1; i <= n; i++) {\n        if (F(i) == F(i + n)) {\n            printf(\"0\\n\");\n            return 0;\n        }\n    }\n    int cnt = 0;\n    for (int i = 1; i <= 2 * n; i++) {\n        if (F(i) == i) {\n            cnt++;\n        }\n    }\n    cnt \/= 2;\n    printf(\"1\");\n    for (int i = 0; i < cnt; i++) {\n        printf(\"0\");\n    }\n    printf(\"\\n\");\n    return 0;\n}\n<\/code><\/pre>\n
Gold<\/h1>\n
G1<\/h2>\n
DFS\u5e8f + \u6811\u72b6\u6570\u7ec4<\/p>\n
x\u5230y\u8def\u5f84\u4e0a\u6240\u6709\u70b9\u7684\u5f02\u6216\uff0c\u5c31\u662f
\nx\u5230\u6839\u8282\u70b9\u6240\u6709\u70b9\u7684\u5f02\u6216 ^ y\u5230\u6839\u8282\u70b9\u6240\u6709\u70b9\u7684\u5f02\u6216 ^ LCA(x, y)\u7684\u70b9\u6743\u3002<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n, q;\nvector<int> a[100020];\nint f[100020][20];\nint d[100020];\nint c[200020];\nint w[100020];\nint L[100020];\nint R[100020];\nint ss;\nvoid change(int x, int y) {\n    for (int i = x; i <= 2 * n; i += i & -i) {\n        c[i] ^= y;\n    }\n}\nint query(int x) {\n    int re = 0;\n    for (int i = x; i > 0; i -= i & -i) {\n        re ^= c[i];\n    }\n    return re;\n}\nvoid dfs(int x, int y) {\n    f[x][0] = y;\n    d[x] = d[y] + 1;\n    for (int i = 1; i < 20; i++) {\n        f[x][i] = f[f[x][i - 1]][i - 1];\n    }\n    ss++;\n    L[x] = ss;\n    for (int i: a[x]) {\n        if (i != y) {\n            dfs(i, x);\n        }\n    }\n    ss++;\n    R[x] = ss;\n}\nint lca(int x, int y) {\n    if (d[x] < d[y]) {\n        swap(x, y);\n    }\n    int dd = d[x] - d[y];\n    for (int i = 0; i < 20; i++) {\n        if (dd >> i & 1) {\n            x = f[x][i];\n        }\n    }\n    if (x == y) {\n        return x;\n    }\n    for (int i = 20 - 1; i >= 0; i--) {\n        if (f[x][i] != f[y][i]) {\n            x = f[x][i];\n            y = f[y][i];\n        }\n    }\n    return f[x][0];\n}\nint main() {\n    freopen(\"cowland.in\", \"r\", stdin);\n    freopen(\"cowland.out\", \"w\", stdout);\n    cin >> n >> q;\n    for (int i = 1; i <= n; i++) {\n        cin >> w[i];\n    }\n    for (int i = 1; i < n; i++) {\n        int x, y;\n        cin >> x >> y;\n        a[x].push_back(y);\n        a[y].push_back(x);\n    }\n    dfs(1, 0);\n    for (int i = 1; i <= n; i++) {\n        change(L[i], w[i]);\n        change(R[i], w[i]);\n    }\n    for (int i = 0; i < q; i++) {\n        int o, x, y;\n        cin >> o >> x >> y;\n        if (o == 1) {\n            change(L[x], w[x] ^ y);\n            change(R[x], w[x] ^ y);\n            w[x] = y;\n        } else {\n            cout << (query(L[x]) ^ query(L[y]) ^ w[lca(x, y)]) << endl;\n        }\n    }\n    return 0;\n}\n<\/code><\/pre>\n
G2<\/h2>\n
\u4e8c\u5206\uff0c\u8d2a\u5fc3\u3002<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n, a[100020];\nvector<int> b[100020];\nbool ok(int M) {\n    int cnt = 0;\n    int st = 0;\n    for (int i = 0; i < M; i++) {\n        b[i].clear();\n    }\n    int last = 0;\n    for (int i = 1; i <= M; i++) {\n        if (a[i] < last) {\n            return false;\n        }\n        if (st == cnt) {\n            b[cnt].push_back(a[i]);\n            cnt++;\n        } else if (a[i] > b[cnt - 1][0]) {\n            b[cnt].push_back(a[i]);\n            cnt++;\n        } else {\n            int left = st - 1;\n            int right = cnt;\n            while (left < right - 1) {\n                int mid = (left + right) \/ 2;\n                if (a[i] < b[mid][0]) {\n                    right = mid;\n                } else {\n                    left = mid;\n                }\n            }\n            if (a[i] < b[right].back()) {\n                b[right].push_back(a[i]);\n            } else {\n                st = right;\n                while (a[i] > b[right].back()) {\n                    last = b[right].back();\n                    b[right].pop_back();\n                }\n                b[right].push_back(a[i]);\n            }\n        }\n\/\/      for (int j = st; j <= cnt; j++) {\n\/\/          for (int k: b[j]) {\n\/\/              cout << k << ' ';\n\/\/          }\n\/\/          cout << endl;\n\/\/      }\n    }\n    return true;\n}\nint main() {\n    freopen(\"dishes.in\", \"r\", stdin);\n    freopen(\"dishes.out\", \"w\", stdout);\n    cin >> n;\n    for (int i = 1; i <= n; i++) {\n        cin >> a[i];\n    }\n    int L = 0;\n    int R = n + 1;\n    while (L < R - 1) {\n        int M = (L + R) \/ 2;\n        if (ok(M)) {\n            L = M;\n        } else {\n            R = M;\n        }\n    }\n    cout << L << endl;\n    return 0;\n}\n<\/code><\/pre>\n
G3<\/h2>\n
\u6ce8\u610f\u9009\u62e9\u76842\u4e2a\u77e9\u5f62\u4e0d\u80fd\u6709\u4efb\u4f55\u91cd\u53e0\u7684\u90e8\u5206\u3002
\n\u8fd9\u6837\u9884\u5904\u7406\u51fa\u6765\u524d\u540e\u51e0\u884c\u7684\u7ed3\u679c\uff0c\u524d\u540e\u51e0\u5217\u7684\u7ed3\u679c\u3002\u679a\u4e3e\u5206\u5272\u7ebf\u5373\u53ef\u3002<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\nconst int L = 200;\nint n, k;\nint a[220][220];\nint b[220][220];\nint c[220][220];\nint cL[220];\nint cR[220];\nint rT[220];\nint rB[220];\nvoid gao(int a[220][220]) {\n    for (int i = 1; i <= L; i++) {\n        for (int j = 1; j <= L; j++) {\n            a[i][j] += a[i][j - 1];\n        }\n    }\n    for (int i = 1; i <= L; i++) {\n        for (int j = 1; j <= L; j++) {\n            a[i][j] += a[i - 1][j];\n        }\n    }\n}\nint main() {\n    freopen(\"paintbarn.in\", \"r\", stdin);\n    freopen(\"paintbarn.out\", \"w\", stdout);\n    cin >> n >> k;\n    for (int i = 0; i < n; i++) {\n        int x1, y1, x2, y2;\n        cin >> x1 >> y1 >> x2 >> y2;\n        x1++;\n        y1++;\n        x2++;\n        y2++;\n        a[x1][y1]++;\n        a[x1][y2]--;\n        a[x2][y1]--;\n        a[x2][y2]++;\n    }\n    gao(a);\n    int cnt = 0;\n    for (int i = 1; i <= L; i++) {\n        for (int j = 1; j <= L; j++) {\n            if (a[i][j] == k) {\n                b[i][j] = 1;\n            }\n            if (a[i][j] == k - 1) {\n                c[i][j] = 1;\n            }\n        }\n    }\n    gao(b);\n    gao(c);\n    int ans = 0;\n    for (int i1 = 0; i1 < L; i1++) {\n        for (int i2 = i1 + 1; i2 <= L; i2++) {\n            int tmp = 0;\n            for (int j = 1; j <= L; j++) {\n                int dd = 0;\n                dd -= (b[i2][j] - b[i1][j]) - (b[i2][j - 1] - b[i1][j - 1]);\n                dd += (c[i2][j] - c[i1][j]) - (c[i2][j - 1] - c[i1][j - 1]);\n                tmp += dd;\n                tmp = max(tmp, 0);\n                cL[j] = max(cL[j], tmp);\n            }\n        }\n    }\n    for (int i1 = 0; i1 < L; i1++) {\n        for (int i2 = i1 + 1; i2 <= L; i2++) {\n            int tmp = 0;\n            for (int j = L; j >= 1; j--) {\n                int dd = 0;\n                dd -= (b[i2][j] - b[i1][j]) - (b[i2][j - 1] - b[i1][j - 1]);\n                dd += (c[i2][j] - c[i1][j]) - (c[i2][j - 1] - c[i1][j - 1]);\n                tmp += dd;\n                tmp = max(tmp, 0);\n                cR[j] = max(cR[j], tmp);\n            }\n        }\n    }\n    for (int j1 = 0; j1 < L; j1++) {\n        for (int j2 = j1 + 1; j2 <= L; j2++) {\n            int tmp = 0;\n            for (int i = 1; i <= L; i++) {\n                int dd = 0;\n                dd -= (b[i][j2] - b[i][j1]) - (b[i - 1][j2] - b[i - 1][j1]);\n                dd += (c[i][j2] - c[i][j1]) - (c[i - 1][j2] - c[i - 1][j1]);\n                tmp += dd;\n                tmp = max(tmp, 0);\n                rT[i] = max(rT[i], tmp);\n            }\n        }\n    }\n    for (int j1 = 0; j1 < L; j1++) {\n        for (int j2 = j1 + 1; j2 <= L; j2++) {\n            int tmp = 0;\n            for (int i = L; i >= 1; i--) {\n                int dd = 0;\n                dd -= (b[i][j2] - b[i][j1]) - (b[i - 1][j2] - b[i - 1][j1]);\n                dd += (c[i][j2] - c[i][j1]) - (c[i - 1][j2] - c[i - 1][j1]);\n                tmp += dd;\n                tmp = max(tmp, 0);\n                rB[i] = max(rB[i], tmp);\n            }\n        }\n    }\n    int maxcL = 0;\n    int maxrT = 0;\n    for (int i = 1; i <= L + 1; i++) {\n        maxcL = max(maxcL, cL[i-1]);\n        maxrT = max(maxrT, rT[i-1]);\n        ans = max(ans, maxcL + cR[i]);\n        ans = max(ans, maxrT + rB[i]);\n    }\n    ans += b[L][L];\n    cout << ans << endl;\n    return 0;\n}\n<\/code><\/pre>\n
Platinum<\/h1>\n
P1<\/h2>\n
\u6ce8\u610f\u5230\u5982\u679c\u8d77\u70b9\u76f8\u540c\uff0c\u90a3\u4e48\u968f\u7740\u7ec8\u70b9\u5411\u53f3\u79fb\u52a8\uff0c\u6700\u4f18\u89e3\u662f\u5355\u5cf0\u7684\u3002<\/p>\n
\u5e76\u4e14\u968f\u7740\u5de6\u7aef\u70b9\u4ece\u5de6\u5411\u53f3\u79fb\u52a8\uff0c\u53f3\u7aef\u70b9\u7684\u6700\u4f18\u89e3\u662f\u5355\u8c03\u7684\u3002<\/p>\n
\u6240\u4ee5\u5c31\u662f\u53cc\u6307\u9488\u6cd5\u3002<\/p>\n
\u6ce8\u610f\u5230\u4e00\u4e2a\u533a\u95f4\u7684\u7b54\u6848\u662f
\n(1-p1)(1-p2)..(1-pn) * (p1\/(1-p1) + p2\/(1-p2) + … + pn\/(1-pn))<\/p>\n
\u5206\u522b\u7ef4\u62a4\u524d\u540e2\u90e8\u5206\uff0c\u8fd9\u6837\u5c31\u53ef\u4ee5\u652f\u6301\u5728\u672b\u5c3e\u8ffd\u52a0\u4e00\u4e2a\u6982\u7387\uff0c\u548c\u5220\u6389\u7b2c\u4e00\u4e2a\u6982\u7387\u3002<\/p>\n
\u7591\u4f3c\u9700\u8981\u5904\u7406\u7cbe\u5ea6\u7206\u70b8\u7684\u95ee\u9898\uff08\u7591\u4f3c\u9700\u8981\u53d6\u5bf9\u6570\uff09<\/p>\n
\u5982\u679c\u5de6\u7aef\u70b9\u662fi\uff0c\u53f3\u7aef\u70b9\u7684\u6700\u4f18\u4f4d\u7f6e\u662fbest[i] \uff08\u5982\u679c\u6709\u591a\u4e2a\u6700\u4f18\u4f4d\u7f6e\uff0c\u8ba4\u4e3a\u662f\u6700\u5de6\u7684\uff09
\n\u90a3\u4e48best[i]\u6570\u7ec4\u662f\u5355\u8c03\u589e\u52a0\u7684\u3002<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n;\nlong double p[1000020];\nint main() {\n    freopen(\"cowdate.in\", \"r\", stdin);\n    freopen(\"cowdate.out\", \"w\", stdout);\n    long double ans = 0;\n    cin >> n;\n    for (int i = 1; i <= n; i++) {\n        cin >> p[i];\n        p[i] \/= 1e6;\n        ans = max(ans, (long double)p[i]);\n    }\n    if (n <= 4000) {\n        ans = 0;\n        for (int i = 1; i <= n; i++) {\n            long double f = 0;\n            long double g = 0;\n            for (int j = i; j <= n; j++) {\n                f += log(1 - p[j]);\n                g += p[j] \/ (1 - p[j]);\n                ans = max(ans, exp(f) * g);\n            }\n        }\n        printf(\"%d\\n\", (int)(1000000 * ans + 1e-6));\n        return 0;\n    }\n    long double f = 0;\n    long double g = 0;\n    int j = 1;\n    for (int i = 1; i <= n; i++) {\n        while (j <= n && exp(f) * g < exp(f + log(1 - p[j])) * (g + p[j] \/ (1 - p[j]))) {\n            f += log(1 - p[j]);\n            g += p[j] \/ (1 - p[j]);\n            ans = max(ans, exp(f) * g);\n            j++;\n        }\n        f -= log(1 - p[i]);\n        g -= p[i] \/ (1 - p[i]);\n    }\n    printf(\"%d\\n\", (int)(1000000 * ans + 0.13));\n}\n<\/code><\/pre>\n
P2<\/h2>\n
\u9996\u5148\u4e0d\u8003\u8651y\u7b97\u4e00\u4e2a\u5168\u90e8\u7684\u7b54\u6848\u3002<\/p>\n
\u7136\u540e\u51cf\u53bb\u8003\u8651y\u4e0d\u5408\u6cd5\u7684\u3002<\/p>\n
\u8fd9\u662f\u4e00\u4e2a\u80cc\u5305\uff0c\u5bf9\u4e8e\u6bcf\u68f5\u6811\u9700\u8981\u9884\u5904\u7406\u51fa\u6765\u6240\u6709\u8def\u5f84\u7684\u957f\u5ea6\u3002<\/p>\n
(\u6bcf\u4e2a\u6811\u9009\u4e00\u4e2a\u8def\u5f84\uff0c\u52a0\u4e0a(n-m) * x) < y \u95ee\u65b9\u6848\u6570<\/p>\n
\u7136\u540e\u6700\u540e\u8fd8\u8981\u4e58\u4e0a\u4e00\u4e2a\u73af\u6392\u5217\uff08\u4e0d\u540c\u5b50\u6811\u7684\u987a\u5e8f\u4e0d\u5b9a\uff09<\/p>\n
\u518d\u9664\u4ee52\uff08\u987a\u65f6\u9488\u548c\u9006\u65f6\u9488\u7b97\u4f5c\u76f8\u540c\uff09<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\nconst int mod = 1000000007;\nvector<pair<int, int> > a[2520];\nlong long ans = 0;\nlong long cnt = 1;\nlong long sum;\nint sz;\nbool v[2520];\nlong long inv[2520];\nlong long f[2520];\nlong long g[2520];\nint n, m, x, y;\nint dfs(int x, int y) {\n    v[x] = true;\n    int re = 1;\n    for (pair<int, int> i: a[x]) {\n        if (i.first != y) {\n            int tmp = dfs(i.first, x);\n            re += tmp;\n            sum += (long long)i.second * tmp * (sz - tmp);\n        }\n    }\n    return re;\n}\nmap<int, int> c;\nmap<int, int> gao(int x, int y) {\n    v[x] = true;\n    map<int, int> re;\n    re[0] = 1;\n    for (pair<int, int> i: a[x]) {\n        if (i.first != y) {\n            map<int, int> tmp = gao(i.first, x);\n            for (pair<int, int> j: re) {\n                for (pair<int, int> k: tmp) {\n                    c[j.first + i.second + k.first] += j.second * k.second * 2;\n                }\n            }\n            for (pair<int, int> k: tmp) {\n                re[i.second + k.first] += k.second;\n            }\n        }\n    }\n    return re;\n}\nint main() {\n    freopen(\"mooriokart.in\", \"r\", stdin);\n    freopen(\"mooriokart.out\", \"w\", stdout);\n    cin >> n >> m >> x >> y;\n    inv[1] = 1;\n    for (int i = 2; i <= n; i++) {\n        inv[i] = inv[mod % i] * (mod - mod \/ i) % mod;\n    }\n    if ((n - m) * x <= y) {\n        f[(n - m) * x] = 1;\n    }\n\n    for (int i = 0; i < m; i++) {\n        int x, y, z;\n        cin >> x >> y >> z;\n        a[x].push_back(make_pair(y, z));\n        a[y].push_back(make_pair(x, z));\n    }\n\n    memset(v, 0, sizeof v);\n    for (int i = 1; i <= n; i++) {\n        if (!v[i]) {\n            sz = dfs(i, 0);\n            cnt = cnt * sz % mod * (sz - 1) % mod;\n        }\n    }\n\n    memset(v, 0, sizeof v);\n    for (int i = 1; i <= n; i++) {\n        if (!v[i]) {\n            sz = dfs(i, 0);\n            sum = 0;\n            dfs(i, 0);\n            ans = (ans + cnt * inv[sz] % mod * inv[sz-1] % mod * sum % mod) % mod;\n        }\n    }\n\n    ans *= 2;\n\n    ans = (ans + cnt * (n - m) * x) % mod;\n\n    memset(v, 0, sizeof v);\n    for (int i = 1; i <= n; i++) {\n        if (!v[i]) {\n            c.clear();\n            gao(i, 0);\n            memset(g, 0, sizeof g);\n\/\/          for (pair<int, int> i: c) {\n\/\/              cout << i.first << ' ' << i.second << endl;\n\/\/          }\n\/\/          cout << endl;\n            for (pair<int, int> i: c) {\n                for (int j = i.first; j <= y; j++) {\n                    g[j] = (g[j] + f[j - i.first] * i.second) % mod;\n                }\n            }\n            swap(f, g);\n        }\n    }\n\/\/  for (int i = 0; i <= y; i++) {\n\/\/      cout << i << ' ' << f[i] << endl;\n\/\/  }\n    for (int i = 0; i < y; i++) {\n        ans = (ans - (long long)i * f[i] % mod + mod) % mod;\n    }\n\n    for (int i = 1; i < n - m; i++) {\n        ans = ans * i % mod;\n    }\n\n    if (ans & 1) {\n        ans += mod;\n    }\n    ans \/= 2;\n    cout << ans << endl;\n    return 0;\n}\n<\/code><\/pre>\n
P3<\/h2>\n
\u8f93\u5165(0, 0)\u5230(T, T)\u77e9\u5f62\u5185\u7684n\u4e2a\u70b9\u3002<\/p>\n
\u4ece(0, 0)\u5230(T, T)\u53ea\u80fd\u5411\u6b63\u65b9\u5411\u8d70\uff0c\u5e0c\u671b\u7ecf\u8fc7\u6700\u591a\u7684\u70b9\uff08\u6700\u957f\u4e0a\u5347\u5b50\u5e8f\u5217\uff09<\/p>\n
\u5982\u679c\u4ece(x1, y1)\u8d70\u5230(x2, y2)\u90a3\u4e48\u4ee3\u4ef7\u662f(x2-x1) * (y2-y1)<\/p>\n
\u95ee\u6240\u6709\u7ecf\u8fc7\u6700\u591a\u70b9\u7684\u8def\u5f84\uff0c\u6743\u503c\u6700\u5c0f\u7684\u662f\u591a\u5927\uff1f<\/p>\n
T <= 1e6
\nn <= 2e5
\nn\u4e2a\u70b9\u4e2d\uff0c\u4efb\u610f2\u4e2a\u70b9\uff0c\u4e0d\u4f1a\u5728\u540c\u4e00\u884c\u6216\u540c\u4e00\u5217\u3002<\/p>\n
\u9996\u5148\u8bf4\u8bf4\u9898\u76ee\u4e2d\u7684\u54ea\u4e9b\u6761\u4ef6\u6709\u7528\uff0c\u54ea\u4e9b\u6ca1\u7528\u5427\u3002
\nT\u7684\u8303\u56f4\u57fa\u672c\u6ca1\u7528\u3002
\n\u4efb\u610f2\u4e2a\u70b9\uff0c\u4e0d\u4f1a\u5728\u540c\u4e00\u884c\u6216\u540c\u4e00\u5217\uff0c\u53ef\u4ee5\u53bb\u6389\uff0c\u4f46\u662f\u5b9e\u73b0\u8d77\u6765\u4f1a\u9ebb\u70e6\u5f88\u591a\u3002
\n\u6700\u5173\u952e\u7684\u662f\u7ecf\u8fc7\u6700\u591a\u70b9\u7684\u8def\u5f84\u3002<\/p>\n
\u76f4\u63a5\u66b4\u529b\u662fn^2\u7684<\/p>\n
\u7136\u540e\u5047\u8bbe\u6c42\u51fa\u4e86\u6700\u957f\u4e0d\u4e0b\u964d\u5b50\u5e8f\u5217
\n\u6bcf\u4e2a\u70b9\u5728\u6700\u957f\u4e0d\u4e0b\u964d\u5b50\u5e8f\u5217\u4e2d\u7684\u4f4d\u7f6e\u662f\u786e\u5b9a\u7684\u3002
\n\u52a8\u6001\u89c4\u5212\u4e2d\u53ea\u9700\u8981\u8003\u8651\u76f8\u90bb\u4e24\u4e2a\u4f4d\u7f6e\u4e4b\u95f4\u7684\u5173\u7cfb\u5373\u53ef\u3002<\/p>\n
\u8fd9\u4e2a\u4e8b\u60c5\u7528\u66b4\u529b\u6765\u505a\u8fd8\u662fn^2\u7684
\n\u600e\u4e48\u505a\u66f4\u5feb\u5462\uff1f\u7ebf\u6bb5\u6811\u5206\u6cbb<\/p>\n
\u5bf9\u4e8e\u76f8\u90bb\u4e24\u4e2a\u4f4d\u7f6ei-1\u548ci
\n\u5047\u8bbei-1\u4f4d\u7f6e\u4e0a\u7684\u4efb\u610f\u4e00\u4e2a\u70b9\uff0c\u53ef\u4ee5\u5230i\u4f4d\u7f6e\u4e0a\u7684\u4efb\u610f\u4e00\u4e2a\u70b9\uff0c\u90a3\u4e48\u6709\u4e00\u4e2a\u975e\u5e38\u7b80\u5355\u7684\u53cd\u5411\u5355\u8c03\u6027\u3002
\n\uff08\u8d8a\u9760\u53f3\u4e0b\u7684\u70b9\uff0c\u8d8a\u4f1a\u9009\u5230\u5de6\u4e0a\u7684\u70b9\uff09<\/p>\n
\u4f46\u662f\u5b9e\u9645\u4e0a\uff0c\u5bf9\u4e8e\u7b2ci\u4f4d\u7f6e\u7684\u70b9\uff0c\u4e0d\u662fi-1\u4f4d\u7f6e\u4e0a\u7684\u4efb\u610f\u4e00\u4e2a\u70b9\u90fd\u53ef\u4ee5\uff08\u53ef\u884c\u7684\u662f\u4e00\u4e2a\u533a\u95f4\uff09
\n\u8fd9\u4e2a\u533a\u95f4\u662f\u4e0d\u5305\u542b\u7684\uff08\u8fd9\u4e2a\u6761\u4ef6\u6ca1\u7528\uff09
\n\u5bf9\u4e8e\u7b2ci-1\u5c42\u7684\u70b9\u5efa\u4e00\u4e2a\u7ebf\u6bb5\u6811\u3002<\/p>\n
\u53ef\u4ee5\u7528\u8fd9\u4e2a\u7ebf\u6bb5\u6811\u4e0a\u7684\u4e00\u4e9b\u8282\u70b9\uff0c\u62fc\u51fa \u53ef\u4ee5\u8f6c\u79fb\u5230\u67d0\u70b9\u7684\u533a\u95f4\u3002
\n\u8fd9\u6837\u5bf9\u4e8e\u7ebf\u6bb5\u6811\u4e0a\u6bcf\u4e2a\u8282\u70b9\uff0c\u53ef\u4ee5\u8f6c\u79fb\u5230\u4e00\u4e9b\u70b9\u3002
\n\u8fd9\u4e2a\u95ee\u9898\u5c31\u8f6c\u5316\u4e3a\u4e86
\n\u300c\u5047\u8bbei-1\u4f4d\u7f6e\u4e0a\u7684\u4efb\u610f\u4e00\u4e2a\u70b9\uff0c\u53ef\u4ee5\u5230i\u4f4d\u7f6e\u4e0a\u7684\u4efb\u610f\u4e00\u4e2a\u70b9\uff0c\u90a3\u4e48\u6709\u4e00\u4e2a\u975e\u5e38\u7b80\u5355\u7684\u53cd\u5411\u5355\u8c03\u6027\u3002\u300d<\/p>\n
\u603b\u65f6\u95f4\u590d\u6742\u5ea6\u5927\u6982\u662f$O(n \\log^2 n)$\u3002<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n;\npair<int, int> points[1000020];\nint lastmin[1000020];\nlong long t;\nvector<pair<int, int> > group[200020];\nvector<long long> dp[200020];\nvector<int> querys[800020];\n\nvoid build(int x, int l, int r) {\n    querys[x].clear();\n    if (l == r) {\n        return;\n    }\n    int mid = (l + r) \/ 2;\n    build(x * 2, l, mid);\n    build(x * 2 + 1, mid + 1, r);\n}\n\nvoid change(int x, int l, int r, int L, int R, int v) {\n    if (L <= l && r <= R) {\n        querys[x].push_back(v);\n        return;\n    }\n    if (R < l || r < L) {\n        return;\n    }\n    int mid = (l + r) \/ 2;\n    change(x * 2, l, mid, L, R, v);\n    change(x * 2 + 1, mid + 1, r, L, R, v);\n}\n\nvoid solve(const vector<int> &querys, int l, int r, int L, int R, int index) {\n    if (l > r) {\n        return;\n    }\n    int mid = (l + r) \/ 2;\n    int j = querys[mid];\n    long long best = 1e18;\n    int pos = -1;\n    for (int k = L; k <= R; k++) {\n        int dx = (group[index][j].first - group[index - 1][k].first);\n        int dy = (group[index][j].second - group[index - 1][k].second);\n        if (dx > 0 && dy > 0) {\n            long long tmp = dp[index - 1][k] + (long long)dx * dy;\n            if (best > tmp) {\n                best = tmp;\n                pos = k;\n            }\n        }\n    }\n    assert(pos != -1);\n    dp[index][j] = min(dp[index][j], best);\n    solve(querys, l, mid - 1, pos, R, index);\n    solve(querys, mid + 1, r, L, pos, index);\n}\n\nvoid query(int x, int l, int r, int index) {\n    \/*\n    if (index == 2) {\n        cerr << \"tree \" << x << ' ' << l << ' ' << r <<  \": \";\n        for (int i: querys[x]) {\n            cerr << i << ' ';\n        }\n        cerr << endl;\n    }\n    *\/\n    solve(querys[x], 0, querys[x].size() - 1, l, r, index);\n    if (l == r) {\n        return;\n    }\n    int mid = (l + r) \/ 2;\n    query(x * 2, l, mid, index);\n    query(x * 2 + 1, mid + 1, r, index);\n}\n\nint main() {\n    freopen(\"mowing.in\", \"r\", stdin);\n    freopen(\"mowing.out\", \"w\", stdout);\n    cin >> n >> t;\n    for (int i = 1; i <= n; i++) {\n        cin >> points[i].first >> points[i].second;\n    }\n    points[n + 1] = make_pair(t, t);\n    sort(points, points + n + 2);\n    for (int i = 0; i < n + 2; i++) {\n        lastmin[i] = 1e9;\n    }\n    int length = 0;\n    for (int i = 0; i < n + 2; i++) {\n        int L = -1;\n        int R = n + 2;\n        while (L < R - 1) {\n            int M = (L + R) \/ 2;\n            if (lastmin[M] < points[i].second) {\n                L = M;\n            } else {\n                R = M;\n            }\n        }\n        lastmin[R] = points[i].second;\n        group[R].push_back(points[i]);\n        length = max(length, R);\n    }\n    dp[0].resize(1);\n    dp[0][0] = 0;\n    for (int i = 1; i <= length; i++) {\n        dp[i].resize(group[i].size());\n        build(1, 0, dp[i-1].size() - 1);\n        for (int j = 0; j < group[i].size(); j++) {\n            dp[i][j] = 1e18;\n            int st = -1, ed = -1;\n            {\n                int L = -1, R = group[i-1].size();\n                while (L < R - 1) {\n                    int M = (L + R) \/ 2;\n                    if (group[i-1][M].second > group[i][j].second) {\n                        L = M;\n                    } else {\n                        R = M;\n                    }\n                }\n                st = R;\n            }\n            {\n                int L = -1, R = group[i-1].size();\n                while (L < R - 1) {\n                    int M = (L + R) \/ 2;\n                    if (group[i-1][M].first > group[i][j].first) {\n                        R = M;\n                    } else {\n                        L = M;\n                    }\n                }\n                ed = L;\n            }\n            change(1, 0, group[i-1].size() - 1, st, ed, j);\n        }\n        query(1, 0, group[i-1].size() - 1, i);\n        \/*\n        cerr << i << \": \";\n        for (int j = 0; j < group[i].size(); j++) {\n            cerr << dp[i][j] << ' ';\n        }\n        cerr << endl;\n\/\/      *\/\n    }\n    cout << dp[length][0] << endl;\n    return 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[4],"class_list":["post-158","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-usaco"],"_links":{"self":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts\/158","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/comments?post=158"}],"version-history":[{"count":0,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts\/158\/revisions"}],"wp:attachment":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/media?parent=158"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/categories?post=158"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/tags?post=158"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}