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

void solve() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vector<bool> vis(n + 1, false);
    rep(i, 0, n - 1) {
        if (a[i] != 0) vis[a[i]] = true;
    }
    int re = n;
    rep(i, 0, n - 1) {
        if (a[i]) continue;
        while (re >= 1 && vis[re]) re--;
        a[i] = re;
        vis[re] = true;
    }
    int l = 0, r = n - 1;
    while (l <= n - 1 && a[l] == l + 1) l++;
    while (r >= 0 && a[r] == r + 1) r--;
    if (r <= l)
        cout << 0 << endl;
    else
        cout << r - l + 1 << endl;
    return;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

const ll MOD = 998244353;
void solve() {
    int n;
    cin >> n;
    vi a(n);
    vi b(n);
    rep(i, 0, n - 1) cin >> a[i];
    rep(i, 0, n - 1) cin >> b[i];
    vvl dp(n, vl(2, 0));
    dp[0][0] = 1, dp[0][1] = 1;
    rep(i, 1, n - 1) {
        if (a[i] >= a[i - 1] && b[i] >= b[i - 1]) dp[i][0] = (dp[i][0] + dp[i - 1][0]) % MOD;
        if (a[i] >= b[i - 1] && b[i] >= a[i - 1]) dp[i][0] = (dp[i][0] + dp[i - 1][1]) % MOD;
        if (a[i] >= b[i - 1] && b[i] >= a[i - 1]) dp[i][1] = (dp[i][1] + dp[i - 1][0]) % MOD;
        if (a[i] >= a[i - 1] && b[i] >= b[i - 1]) dp[i][1] = (dp[i][1] + dp[i - 1][1]) % MOD;
    }
    cout << (dp[n - 1][0] + dp[n - 1][1]) % MOD << 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

void solve() {
    ll n, y;
    cin >> n >> y;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ranges::sort(a);
    int maxx = *max_element(all(a));
    if (maxx == 1) {
        cout << n << endl;
        return;
    }
    vl pre(maxx + 1);
    rep(i, 0, n - 1) pre[a[i]]++;
    rep(i, 1, maxx) pre[i] += pre[i - 1];
    vl cnt(maxx + 1);
    rep(i, 0, n - 1) cnt[a[i]]++;
    ll ans = LLONG_MIN;
    rep(i, 2, maxx) {
        ll tem = 0;
        for (int j = i; j < maxx + i; j += i) {
            if (j >= maxx) {
                ll tem2 = pre[maxx] - pre[j - i];
                if (tem2 == 0) continue;
                tem += 1LL * (j / i) * tem2 - y * max(0LL, (tem2 - cnt[(j / i)]));
            } else {
                ll tem2 = pre[j] - pre[j - i];
                if (tem2 == 0) continue;
                tem += 1LL * (j / i) * tem2 - y * max(0LL, (tem2 - cnt[(j / i)]));
            }
        }
        ans = max(ans, tem);
    }
    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
80
81
82
83
84
85
86
87
88
89
90
91

constexpr int MOD = 998244353;
int mul(int x, int y) { return x * 1LL * y % MOD; }
int qpow(int x, int y) {
    int z = 1;
    while (y > 0) {
        if (y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}  // 求x**y%MOD

// 注意：当MOD为质数时， (x/y)%MOD=(x*(y**(MOD-2)))%MOD，即y在模MOD意义下的逆元为b^{-1} \equiv b^{p-2} mod p

void solve() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll ans = 0;
    int tem = a[0];
    vi l;
    l.push_back(a[0]);
    rep(i, 1, n - 1) {
        if (a[i] > tem) {
            l.push_back(a[i]);
            tem = a[i];
        }
    }
    int lz = sz(l);
    tem = a[n - 1];
    vi r;
    r.push_back(a[n - 1]);
    frep(i, n - 2, 0) {
        if (a[i] > tem) {
            r.push_back(a[i]);
            tem = a[i];
        }
    }
    int rz = sz(r);
    int maxx = *max_element(all(a));
    vi te;
    rep(i, 0, n - 1) {
        if (a[i] == maxx) te.push_back(i);
    }
    int m = sz(te);
    vvl dp1(n + 1, vl(lz + 1));
    rep(i, 0, n) dp1[i][0] = 1;
    rep(i, 1, n) {
        rep(j, 1, lz) {
            dp1[i][j] = (dp1[i][j] + dp1[i - 1][j]) % MOD;
            if (a[i - 1] <= l[j - 1]) {
                dp1[i][j] = (dp1[i][j] + dp1[i - 1][j]) % MOD;
            }
            if (a[i - 1] == l[j - 1]) {
                dp1[i][j] = (dp1[i][j] + dp1[i - 1][j - 1]) % MOD;
            }
        }
    }
    ranges::reverse(a);
    vvl dp2(n + 1, vl(rz + 1));
    rep(i, 0, n) dp2[i][0] = 1;
    rep(i, 1, n) {
        rep(j, 1, rz) {
            dp2[i][j] = (dp2[i][j] + dp2[i - 1][j]) % MOD;
            if (a[i - 1] <= r[j - 1]) {
                dp2[i][j] = (dp2[i][j] + dp2[i - 1][j]) % MOD;
            }
            if (a[i - 1] == r[j - 1]) {
                dp2[i][j] = (dp2[i][j] + dp2[i - 1][j - 1]) % MOD;
            }
        }
    }
    rep(i, 0, m - 1) {
        rep(j, i, m - 1) {
            if (i == j) {
                int tem3 = te[i];
                ans += 1LL * dp1[tem3][lz - 1] * dp2[n - 1 - tem3][rz - 1] % MOD;
                ans %= MOD;
            } else {
                int le = te[i];
                int re = te[j];
                ll tem4 = dp1[le][lz - 1] * dp2[n - 1 - re][rz - 1] % MOD;
                ans += mul(qpow(2, re - le - 1), tem4);
                ans %= MOD;
            }
        }
    }
    cout << ans << endl;
    return;
}