QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #588812 | #8772. House Deconstruction | hos_lyric | AC ✓ | 48ms | 16332kb | C++14 | 3.4kb | 2024-09-25 14:42:04 | 2024-09-25 14:42:06 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
/*
no arc in both directions
P ---> H
P' ---> H'
->
P -------> H'
P'->H
==> each P has unique mate in each direction
*/
constexpr Int INF = 1001001001001001001LL;
constexpr int MO = 998244353;
Int L;
int N, N0, N1;
vector<Int> X;
vector<char> T;
vector<int> getTo() {
vector<int> to(N, -1);
vector<int> us(4 * N, -1);
int d = 2 * N;
for (int h = 0; h < 2; ++h) for (int u = 0; u < N; ++u) {
if (T[u] == 'P') {
us[d] = u;
++d;
} else if (T[u] == 'H') {
--d;
if (~us[d]) to[us[d]] = u;
} else {
assert(false);
}
}
return to;
}
Int dist(int u, int v) {
return X[v] - X[u] + ((u > v) ? L : 0);
}
int main() {
for (; ~scanf("%lld%d%d", &L, &N0, &N1); ) {
N = N0 + N1;
X.resize(N);
T.resize(N);
for (int u = 0; u < N; ++u) {
scanf("%lld %c", &X[u], &T[u]);
}
auto toR = getTo(); reverse(T.begin(), T.end());
auto toL = getTo(); reverse(T.begin(), T.end());
reverse(toL.begin(), toL.end());
for (int u = 0; u < N; ++u) if (~toL[u]) toL[u] = N - 1 - toL[u];
// cerr<<"toL = "<<toL<<endl;
// cerr<<"toR = "<<toR<<endl;
for (int u = 0; u < N; ++u) if (T[u] == 'P') {
if (~toL[u]) toR[toL[u]] = u;
if (~toR[u]) toL[toR[u]] = u;
}
Int ansMn = 0;
Int ansWay = 1;
for (int s = 0; s < N; ++s) if (!~toL[s]) {
vector<int> path;
for (int u = s; ; ) {
path.push_back(u);
if (!~toR[u]) break;
u = toR[u];
}
assert(path.size() & 1);
const int len = (int)path.size() / 2;
vector<Int> pre(len + 1, 0), suf(len + 1, 0);
for (int j = 0; j < len; ++j) pre[j + 1] = pre[j] + dist(path[j * 2], path[j * 2 + 1]);
for (int j = len; --j >= 0; ) suf[j] = dist(path[j * 2 + 1], path[j * 2 + 2]) + suf[j + 1];
Int mn = INF;
int way = 0;
for (int j = 0; j <= len; ++j) {
if (chmin(mn, pre[j] + suf[j])) way = 0;
if (mn == pre[j] + suf[j]) ++way;
}
ansMn += mn;
(ansWay *= way) %= MO;
}
printf("%lld\n", ansMn);
printf("%lld\n", ansWay);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3800kb
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: 3888kb
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: 48ms
memory: 16304kb
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: 44ms
memory: 14672kb
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: 34ms
memory: 12844kb
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: 41ms
memory: 14440kb
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: 30ms
memory: 16140kb
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: 22ms
memory: 12244kb
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: 28ms
memory: 12012kb
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: 36ms
memory: 16332kb
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: 37ms
memory: 16144kb
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: 32ms
memory: 16100kb
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: 26ms
memory: 12844kb
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: 38ms
memory: 13636kb
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