QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#428155#8772. House Deconstructionucup-team004#AC ✓322ms10000kbC++208.1kb2024-06-01 17:45:212024-06-01 17:45:22

Judging History

你现在查看的是最新测评结果

  • [2024-06-01 17:45:22]
  • 评测
  • 测评结果:AC
  • 用时:322ms
  • 内存:10000kb
  • [2024-06-01 17:45:21]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

constexpr i64 inf = 1E18;
template<class T>
constexpr T power(T a, i64 b) {
    T res {1};
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}

template<i64 P>
struct MInt {
    i64 x;
    constexpr MInt() : x {0} {}
    constexpr MInt(i64 x) : x {norm(x % getMod())} {}
    
    static i64 Mod;
    constexpr static i64 getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(i64 Mod_) {
        Mod = Mod_;
    }
    constexpr i64 norm(i64 x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr i64 val() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        if (getMod() < (1ULL << 31)) {
            x = x * rhs.x % int(getMod());
        } else {
            x = mul(x, rhs.x, getMod());
        }
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
    friend constexpr bool operator<(MInt lhs, MInt rhs) {
        return lhs.val() < rhs.val();
    }
};

template<>
i64 MInt<0>::Mod = 998244353;

constexpr int P = 998244353;
using Z = MInt<P>;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int x, n, m;
    std::cin >> x >> n >> m;
    
    const int N = n + m;
    std::vector<int> p(N), d(N);
    std::vector<char> t(N);
    for (int i = 0; i < N; i++) {
        std::cin >> p[i] >> t[i];
    }
    for (int i = 1; i < N; i++) {
        d[i] = p[i] - p[i - 1];
    }
    d[0] = p[0] + x - p[N - 1];
    
    // auto work = [&](int k, int tp = 0) {
    //     std::vector<i64> dp(N + 1, inf);
    //     dp[0] = 0;
    //     std::vector<Z> g(N + 1);
    //     g[0] = 1;
    //     int c = k;
    //     for (int i = 0; i < N; i++) {
    //         for (int j = 0; j <= n; j++) {
    //             dp[j] += 1LL * d[i] * std::abs(j - c);
    //         }
    //         if (t[i] == 'P') {
    //             c++;
    //         } else {
    //             for (int j = n; j > 0; j--) {
    //                 if (dp[j - 1] < dp[j]) {
    //                     dp[j] = dp[j - 1];
    //                     g[j] = g[j - 1];
    //                 } else if (dp[j - 1] == dp[j]) {
    //                     g[j] += g[j - 1];
    //                 }
    //             }
    //         }
    //     }
    //     return std::make_pair(dp[n], g[n]);
    // };
    
    auto work = [&](int k, int tp = 0) {
        // std::cerr << "--- work " << k << "\n";
        int c = k;
        
        std::vector<std::pair<int, int>> seg;
        if (tp) {
            seg.reserve(m);
        }
        
        // std::vector<i64> dp(N + 1, inf);
        // dp[0] = 0;
        // std::vector<Z> g(n + 1);
        // g[0] = 1;
        
        i64 res = 0;
        int lo = 0, hi = 0;
        std::deque<i64> del(n + 1);
        del[0] = inf;
        for (int i = 0; i < N; i++) {
            res += 1LL * d[i] * std::abs(lo - c);
            int v = std::min(n, std::max(0, c));
            assert(v >= lo);
            // std::cerr << "v : " << v << " d : " << d[i] << "\n";
            del[v - lo] += 2 * d[i];
            int cur = -d[i];
            while (lo < n && cur < 0) {
                int t = std::min<i64>(-cur, del[0]);
                del[0] -= t;
                cur += t;
                if (cur == 0) {
                    break;
                }
                res += cur;
                lo++;
                del.pop_front();
            }
            // for (int j = 0; j <= n; j++) {
            //     dp[j] += 1LL * d[i] * std::abs(j - c);
            // }
            if (t[i] == 'P') {
                c++;
            } else {
                if (tp) {
                    // std::cerr << "dp: ";
                    // for (int j = 0; j <= n; j++) {
                    //     std::cerr << dp[j] << " \n"[j == n];
                    // }
                }
                if (hi < lo) {
                    hi = lo;
                }
                while (hi < n && del[hi - lo] == 0) {
                    hi++;
                }
                del.push_front(0);
                if (tp) {
                    seg.emplace_back(lo, hi);
                }
                // if (tp) {
                //     std::cerr << lo << " " << hi << " " << res << "\n";
                // }
                // for (int j = n; j > 0; j--) {
                //     if (dp[j - 1] < dp[j]) {
                //         dp[j] = dp[j - 1];
                //         // g[j] = g[j - 1];
                //     } else if (dp[j - 1] == dp[j]) {
                //         // g[j] += g[j - 1];
                //     }
                // }
            }
        }
        i64 cur = 0;
        for (int i = lo; i < n; i++) {
            cur += del[i - lo];
            res += cur;
        }
        if (!tp) {
            return std::make_pair(res, Z(0));
        }
        std::deque<Z> gl {1}, gr;
        lo = 0, hi = 0;
        for (auto [l, r] : seg) {
            while (hi < r) {
                assert(!gr.empty());
                gl.push_back(gr[0]);
                gr.pop_front();
                hi++;
            }
            while (lo < l) {
                assert(!gl.empty());
                gl.pop_front();
                lo++;
            }
            assert(!gl.empty());
            gr.push_front(gl.back());
            for (int i = hi - lo; i >= 1; i--) {
                gl[i] += gl[i - 1];
            }
        }
        return std::make_pair(res, hi == n ? gl.back() : gr[n - 1 - hi]);
    };
    
    int lo = -n, hi = n;
    while (lo < hi) {
        int m = lo + (hi - lo) / 2;
        if (work(m).first < work(m + 1).first) {
            hi = m;
        } else {
            lo = m + 1;
        }
    }
    
    i64 ans = work(lo).first;
    Z ways = 0;
    for (int i = lo; ; i--) {
        auto [a, b] = work(i, 1);
        if (a != ans) {
            break;
        }
        ways += b;
    }
    for (int i = lo + 1; ; i++) {
        auto [a, b] = work(i, 1);
        if (a != ans) {
            break;
        }
        ways += b;
    }
    std::cout << ans << "\n";
    std::cout << ways << "\n";
    
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3552kb

input:

6 2 4
1 P
2 H
3 P
4 H
5 H
6 H

output:

2
3

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

1000000000 2 4
1 P
6 H
31415926 H
999999998 H
999999999 H
1000000000 P

output:

4
1

result:

ok 2 lines

Test #3:

score: 0
Accepted
time: 322ms
memory: 9816kb

input:

1000000000 199999 200000
3087 P
3282 H
6407 H
6748 P
9535 P
10098 H
16470 H
22311 H
31045 H
31968 H
32549 H
33037 P
36005 P
36308 H
40284 P
46224 H
52394 P
54922 H
55800 P
56582 H
57548 H
62155 P
63067 P
64237 H
66133 P
71351 P
75667 P
79089 P
79646 P
81144 H
91883 P
96680 H
102797 H
105388 H
105971...

output:

262753966206
1

result:

ok 2 lines

Test #4:

score: 0
Accepted
time: 243ms
memory: 10000kb

input:

1000000000 150000 200000
3087 P
3282 H
6407 H
6748 H
9535 H
10098 H
16470 H
22311 H
31968 H
32549 H
33037 P
36005 P
40284 H
52394 P
54922 H
55800 H
56582 H
57548 H
62155 P
63067 P
64237 H
66133 P
71351 P
75667 H
79089 P
79646 P
81144 H
91883 P
96680 H
102797 H
105388 H
105971 P
106057 P
107807 P
116...

output:

1212175277
8

result:

ok 2 lines

Test #5:

score: 0
Accepted
time: 111ms
memory: 9920kb

input:

1000000000 100000 200000
3068 H
3087 P
3106 H
33031 H
33037 P
33043 H
52370 H
52394 P
52418 H
62996 H
63067 P
63138 H
66040 H
66133 P
66226 H
71350 H
71351 P
71352 H
91852 H
91883 P
91914 H
105924 H
105969 H
105971 P
106018 H
106057 P
106145 H
116361 H
116385 P
116409 H
126036 H
126084 P
126132 H
12...

output:

4978306
463697368

result:

ok 2 lines

Test #6:

score: 0
Accepted
time: 244ms
memory: 9944kb

input:

1000000 150000 200000
2 H
3 H
6 H
8 H
16 P
17 H
19 P
20 P
21 P
24 H
28 H
33 H
37 P
38 H
40 H
44 P
48 H
49 P
58 P
59 P
60 H
62 P
65 P
70 H
72 H
76 P
77 H
79 P
84 P
93 H
96 P
101 H
104 H
106 P
110 H
111 P
112 H
116 H
124 P
125 H
126 H
127 H
128 P
134 H
135 P
137 P
138 P
140 H
142 H
145 H
146 H
147 H
1...

output:

1203722
86861366

result:

ok 2 lines

Test #7:

score: 0
Accepted
time: 154ms
memory: 9772kb

input:

1000000000 199999 200000
966788248 H
966788251 P
966788252 H
966788254 P
966788255 H
966788260 P
966788261 H
966788263 P
966788267 H
966788275 P
966788278 H
966788279 P
966788288 H
966788291 P
966788298 H
966788304 P
966788305 H
966788308 P
966788309 H
966788317 P
966788326 H
966788334 P
966788342 H...

output:

1098446
4586

result:

ok 2 lines

Test #8:

score: 0
Accepted
time: 148ms
memory: 8852kb

input:

10000000 137967 139896
52 P
101 H
106 P
149 P
158 P
190 P
258 P
338 P
349 P
350 P
457 P
486 P
500 P
509 P
517 P
563 P
568 P
630 P
723 P
738 P
801 P
819 P
859 P
872 P
885 P
900 P
972 P
1004 P
1034 P
1087 P
1183 P
1236 P
1245 P
1268 P
1436 H
1481 P
1486 P
1511 P
1544 P
1607 P
1647 P
1685 P
1798 P
1819...

output:

317845182248
2

result:

ok 2 lines

Test #9:

score: 0
Accepted
time: 154ms
memory: 8980kb

input:

400000 137967 139896
1 P
2 H
3 P
4 P
5 P
6 P
9 P
10 P
11 P
15 P
16 P
17 P
18 P
19 P
20 P
22 P
23 P
24 P
26 P
27 P
28 P
29 P
31 P
32 P
33 P
34 P
35 P
36 P
37 P
39 P
40 P
45 P
47 P
48 P
49 H
51 P
52 P
53 P
56 P
57 P
58 P
60 P
61 P
62 P
63 P
64 P
65 P
68 P
71 P
72 P
73 P
74 H
75 P
76 P
77 P
78 P
79 P
8...

output:

12717669314
562027925

result:

ok 2 lines

Test #10:

score: 0
Accepted
time: 147ms
memory: 9828kb

input:

1000000000 199000 200000
526190 H
526213 P
526214 H
526299 P
526309 H
526316 P
526351 H
526355 P
526370 H
526400 P
526482 H
526545 P
526569 H
526573 P
526641 H
526658 P
526707 H
526790 P
526838 H
526844 P
526868 H
526967 P
526975 H
527032 P
527097 H
527154 P
527213 H
527278 P
527299 H
527367 P
52743...

output:

9896423
922405585

result:

ok 2 lines

Test #11:

score: 0
Accepted
time: 160ms
memory: 9772kb

input:

1000000000 199950 200000
5239074 H
5239076 P
5239077 H
5239078 P
5239079 H
5239080 P
5239081 H
5239083 P
5239084 H
5239085 P
5239086 H
5239087 P
5239088 H
5239090 P
5239092 H
5239093 P
5239094 H
5239095 P
5239097 H
5239099 P
5239101 H
5239102 P
5239103 H
5239104 P
5239105 H
5239106 P
5239107 H
52391...

output:

299836
463541155

result:

ok 2 lines

Test #12:

score: 0
Accepted
time: 164ms
memory: 9800kb

input:

1000000000 199500 200000
244421 H
244423 P
244424 H
244425 P
244426 H
244427 P
244428 H
244430 P
244431 H
244432 P
244433 H
244434 P
244435 H
244437 P
244439 H
244440 P
244441 H
244442 P
244444 H
244446 P
244448 H
244449 P
244450 H
244451 P
244452 H
244453 P
244454 H
244455 P
244456 H
244458 P
24446...

output:

298242
524810405

result:

ok 2 lines

Test #13:

score: 0
Accepted
time: 158ms
memory: 9384kb

input:

400000 148599 151281
2 P
3 P
5 P
6 P
7 P
8 P
9 P
10 P
11 P
12 P
13 P
14 P
15 P
16 P
17 P
18 P
19 P
22 P
23 P
25 P
30 P
31 P
32 P
33 H
34 P
35 P
36 P
38 P
39 P
40 P
41 P
43 P
45 P
47 P
49 P
50 P
51 P
53 P
54 P
55 P
57 P
58 P
60 H
61 P
62 H
65 P
67 P
68 P
69 P
70 P
71 P
72 P
73 P
74 P
77 P
78 P
79 P
8...

output:

13764808569
268118240

result:

ok 2 lines

Test #14:

score: 0
Accepted
time: 222ms
memory: 9136kb

input:

1000000000 149183 174434
2 H
6 P
10 H
12 H
13 H
14 H
18 P
21 P
23 H
24 H
25 H
30 H
32 H
35 H
37 P
39 P
41 H
53 P
57 H
61 P
62 P
63 P
65 H
66 P
67 H
71 P
73 H
74 P
75 P
76 H
78 H
79 H
80 H
82 P
83 P
84 H
85 H
93 H
95 H
96 P
99 H
107 P
108 P
109 P
111 H
112 P
116 H
118 P
119 H
120 P
121 P
123 H
124 P
...

output:

1788748
930867409

result:

ok 2 lines