1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void solve() {
    ll n, a, b, k;
    cin >> n >> a >> b >> k;
    if (n <= 3) {
        cout << 1 << endl;
        return;
    }
    ll tem = abs(b - a);
    ll tem2 = n - tem;
    cout << min(tem, tem2) + k << endl;
    return;
}

 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

void solve() {
    ll n, a;
    cin >> a >> n;
    string s = to_string(a);
    int m = sz(s);
    vl d(n);
    rep(i, 0, n - 1) cin >> d[i];
    ranges::sort(d);
    ll ans = LLONG_MAX;
    vl tem(m + 1, 1);
    rep(i, 1, m) tem[i] = tem[i - 1] * 10;
    if (m > 1) {
        ll tem2 = 0;
        rep(i, 1, m - 1) tem2 = tem2 * 10 + d[n - 1];
        ans = min(ans, abs(tem2 - a));
    }
    int idx = -1;
    rep(i, 0, n - 1) {
        if (d[i] != 0) {
            idx = i;
            break;
        }
    }
    if (idx != -1) {
        ll tem2 = d[idx];
        rep(i, 2, m + 1) {
            if (tem2 > (LLONG_MAX - d[0]) / 10) {
                tem2 = LLONG_MAX;
                break;
            }
            tem2 = tem2 * 10 + d[0];
        }
        if (tem2 != LLONG_MAX) ans = min(ans, abs(tem2 - a));
    }
    vector<array<int, 3>> vis(m + 1);
    vector<array<ll, 3>> ma(m + 1);
    auto dfs = [&](this auto&& dfs, int pos, int st) -> ll {
        if (pos == m) return 0;
        if (vis[pos][st]) return ma[pos][st];
        vis[pos][st] = 1;
        ll res = LLONG_MAX;
        int tem2 = s[pos] - '0';
        rep(i, 0, n - 1) {
            if (pos == 0 && m > 1 && d[i] == 0) continue;
            ll temp = 0;
            int tx = st;
            if (st == 0) {
                if (d[i] < tem2) {
                    tx = 1;
                    temp += (tem2 - d[i]) * tem[m - pos - 1];
                } else if (d[i] > tem2) {
                    tx = 2;
                    temp += (d[i] - tem2) * tem[m - pos - 1];
                }
            } else if (st == 1) {
                temp += (tem2 - d[i]) * tem[m - pos - 1];
            } else {
                temp += (d[i] - tem2) * tem[m - pos - 1];
            }
            temp += dfs(pos + 1, tx);
            res = min(res, temp);
        }
        ma[pos][st] = res;
        return res;
    };
    cout << min(ans, dfs(0, 0)) << endl;
    return;
}

 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

void solve() {
    ll n, a;
    cin >> a >> n;
    string s = to_string(a);
    int m = sz(s);
    vl d(n);
    rep(i, 0, n - 1) cin >> d[i];
    ranges::sort(d);
    ll ans = LLONG_MAX;
    vl tem(m + 1, 1);
    rep(i, 1, m) tem[i] = tem[i - 1] * 10;
    if (m > 1) {
        ll tem2 = 0;
        rep(i, 1, m - 1) tem2 = tem2 * 10 + d[n - 1];
        ans = min(ans, abs(tem2 - a));
    }
    int idx = -1;
    rep(i, 0, n - 1) {
        if (d[i] != 0) {
            idx = i;
            break;
        }
    }
    if (idx != -1) {
        ll tem2 = d[idx];
        rep(i, 2, m + 1) {
            if (tem2 > (LLONG_MAX - d[0]) / 10) {
                tem2 = LLONG_MAX;
                break;
            }
            tem2 = tem2 * 10 + d[0];
        }
        if (tem2 != LLONG_MAX) ans = min(ans, abs(tem2 - a));
    }
    vector<array<int, 3>> vis(m + 1);
    vector<array<ll, 3>> ma(m + 1);
    auto dfs = [&](this auto&& dfs, int pos, int st) -> ll {
        if (pos == m) return 0;
        if (vis[pos][st]) return ma[pos][st];
        vis[pos][st] = 1;
        ll res = LLONG_MAX;
        int tem2 = s[pos] - '0';
        rep(i, 0, n - 1) {
            if (pos == 0 && m > 1 && d[i] == 0) continue;
            ll temp = 0;
            int tx = st;
            if (st == 0) {
                if (d[i] < tem2) {
                    tx = 1;
                    temp += (tem2 - d[i]) * tem[m - pos - 1];
                } else if (d[i] > tem2) {
                    tx = 2;
                    temp += (d[i] - tem2) * tem[m - pos - 1];
                }
            } else if (st == 1) {
                temp += (tem2 - d[i]) * tem[m - pos - 1];
            } else {
                temp += (d[i] - tem2) * tem[m - pos - 1];
            }
            temp += dfs(pos + 1, tx);
            res = min(res, temp);
        }
        ma[pos][st] = res;
        return res;
    };
    cout << min(ans, dfs(0, 0)) << endl;
    return;
}

 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

void solve() {
    int n;
    cin >> n;
    vector<pll> ma(n);
    rep(i, 0, n - 1) cin >> ma[i].first >> ma[i].second;
    sort(all(ma), [&](const pll& x, const pll& y) {
        if (x.first == y.first) return x.second < y.second;
        return x.first < y.first;
    });
    vl tem;
    rep(i, 0, n - 1) { tem.push_back(ma[i].second); }
    ranges::sort(tem);
    tem.erase(unique(all(tem)), tem.end());
    ll ans = 0;
    ll maxx = LLONG_MIN, mixx = LLONG_MAX;
    vl suf1(n, LLONG_MAX), suf2(n, LLONG_MIN);
    suf1[n - 1] = ma[n - 1].second, suf2[n - 1] = ma[n - 1].second;
    frep(i, n - 2, 0) {
        suf1[i] = min(suf1[i + 1], ma[i].second);
        suf2[i] = max(suf2[i + 1], ma[i].second);
    }
    rep(i, 0, n - 2) {
        maxx = max(maxx, ma[i].second);
        mixx = min(mixx, ma[i].second);
        if (ma[i].first == ma[i + 1].first) continue;
        ll tem2 = max(mixx, suf1[i + 1]);
        ll tem3 = min(maxx, suf2[i + 1]);
        ll cnt = ranges::lower_bound(tem, tem3) - ranges::lower_bound(tem, tem2);
        if (cnt >= 0) ans += cnt;
    }
    cout << ans << endl;
    return;
}

 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

const ll MOD = 998244353;
constexpr int MX = 1e6 + 1;
ll F[MX];      // 预处理阶乘
ll INV_F[MX];  // 预处理逆元
ll qpow(ll x, int n) {
    ll res = 1;
    for (; n; n >>= 1) {
        if (n % 2) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}
auto init = [] {
    F[0] = 1;
    for (int i = 1; i < MX; i++) F[i] = F[i - 1] * i % MOD;  // 预处理阶乘
    INV_F[MX - 1] = qpow(F[MX - 1], MOD - 2);
    for (int i = MX - 1; i; i--) {
        INV_F[i - 1] = INV_F[i] * i % MOD;
    }  // 预处理逆元
    return 0;
}();
// 计算C(n,m),即从n个数中取m个数
ll comb(int n, int m) { return m < 0 || m > n ? 0 : F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD; }
void solve() {
    ll n, q, op, l, r, m;
    cin >> n >> q;
    vl a(n + 1);
    rep(i, 1, n) cin >> a[i];
    vl cnt(n + 1);
    vl pre(n + 1);
    rep(i, 1, n) {
        pre[i] = pre[i - 1];
        cnt[i] = cnt[i - 1];
        if (a[i] == -1)
            cnt[i]++;
        else
            pre[i] = (pre[i - 1] + a[i]);
    }
    rep(v, 0, q - 1) {
        cin >> op >> l >> r >> m;
        ll tem = cnt[r] - cnt[l - 1];
        ll pr = pre[r] - pre[l - 1];
        ll ans = 0;
        if (pr > m) {
            cout << 0 << endl;
            return;
        }
        if (tem == 0) {
            if (pr != m) {
                cout << 0 << endl;
                return;
            }
            ll tem2 = 0;
            rep(i, l, r) {
                tem2 = (tem2 + a[i]) % MOD;
                ans = (ans + tem2 * tem2 % MOD) % MOD;
            }
            cout << ans << endl;
            return;
        }
        ll tem2 = 0;
        ll tem3 = 0;
        ll cnt0 = comb(m - pr + tem - 1, tem - 1);
        ll cnt1 = comb(m - pr + tem - 1, tem);
        ll cnt2 = comb(m - pr + tem - 1, tem + 1);
        rep(i, l, r) {
            if (a[i] == -1)
                tem3++;
            else
                tem2 = (tem2 + a[i]) % MOD;
            ll tem4 = tem3 * cnt1 % MOD;
            ll tem5 = (tem4 + tem3 * (tem3 + 1) % MOD * cnt2 % MOD) % MOD;
            ans = (ans + cnt0 * tem2 % MOD * tem2 % MOD) % MOD;
            ans = (ans + 2 * tem2 % MOD * tem4 % MOD + tem5) % MOD;
        }
        cout << ans << endl;
    }
    return;
}