QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#882938 | #8772. House Deconstruction | ningago | WA | 373ms | 21720kb | C++14 | 8.8kb | 2025-02-05 13:40:57 | 2025-02-05 13:40:58 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <cctype>
#include <set>
namespace uvu
{
#define LOCAL ____________DONT_DEFINE_ME____________
// #define ll long long
// #define inf 0x3f3f3f3f
#define int long long
#define inf 0x3f3f3f3f3f3f3f3fll
#define infll 0x3f3f3f3f3f3f3f3fll
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define gline debug("now is #%d\n", __LINE__)
#define pii std::pair <int, int>
#define mkp std::make_pair
#define fi first
#define se second
char _ST_;
const int BUFSIZE = (1 << 20);
char ibuf[BUFSIZE], *iS = ibuf, *iT = ibuf;
char obuf[BUFSIZE], *oS = obuf, *oT = obuf + BUFSIZE;
char getc()
{
#ifdef LOCAL
return getchar();
#else
if(iS == iT) iT = (iS = ibuf) + fread(ibuf, 1, BUFSIZE, stdin);
return iS == iT ? EOF : *iS++;
#endif
#define getchar ERR
}
void Flush() { fwrite(obuf, 1, oS - obuf, stdout); oS = obuf; }
struct Flusher { ~Flusher(){ Flush(); } }iamflusher;
void putc(char c)
{
#ifdef LOCAL
putchar(c);
#else
*oS++ = c;
if(oS == oT) Flush();
#endif
#define putchar ERR
}
template <typename T = int> T read()
{
T x = 0, f = 1; char c = getc();
for(; !isdigit(c); c = getc()) if(c == '-') f = -1;
for(; isdigit(c); c = getc()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
template <typename T> void print(T x, char c)
{
static int sta[BUFSIZE], top;
top = 0;
if(x < 0) putc('-'), x = -x;
if(!x) sta[top = 1] = 0;
for(; x; x /= 10) sta[++top] = x % 10;
for(; top; ) putc(sta[top--] ^ 48);
if(c) putc(c);
}
int readstr(char *s, int base)
{
int idx = base - 1; char c = getc();
for(; !(isdigit(c) || isalpha(c) || c == '(' || c == '?'); c = getc());
for(; isdigit(c) || isalpha(c) || c == '(' || c == '?' ; c = getc()) s[++idx] = c;
return idx - base + 1;
}
void printf(const char *s) { for(; *s; s++) putc(*s); }
template <typename T, typename ... Args>
void printf(const char *s, T x, Args ... rest)
{
for(; *s; s++)
{
if(*s != '%') { putc(*s); continue; }
s++; if(*s == 'd') print(x, 0);
else if(*s == 'c') putc(x);
printf(s + 1, rest ...);
return;
}
}
template <typename T> void ckmax(T &x, T y) { x = x > y ? x : y; }
template <typename T> void ckmin(T &x, T y) { x = x < y ? x : y; }
#define mod 998244353
// #define mod 1000000007
int sm(int x) { return x >= mod ? x - mod : x; }
void plus_(int &x, int y) { x = (x + y >= mod ? x + y - mod : x + y); }
void mul_(int &x, int y) { x = 1ll * x * y % mod; }
int ksm(int a, int b) { int res = 1; for(; b; b >>= 1, mul_(a, a)) if(b & 1) mul_(res, a); return res; }
#define N 400010
int n, m, A, B;
int op_[N], d[N], x_[N];
char s[2];
std::deque <pii> ql, qr;
int pos, base, val;
int sta[N], top;
int calc(int mid)
{
// printf("mid = %d\n", mid);
// int lim = n + n;
// for(int i = -lim; i <= lim; i++) dp[0][i + DT] = dp[1][i + DT] = (node){inf, 0};
// dp[op = 0][mid + DT] = (node){0, 1};
// for(int i = 1; i <= n; i++)
// {
// op ^= 1;
// for(int j = -lim; j <= lim; j++) dp[op][j + DT] = (node){inf, 0};
// for(int j = -lim; j <= lim; j++)
// {
// if(op_[i] == 0) dp[op][j + DT] += dp[op ^ 1][j + DT] + abs(j) * d[i];
// else if(op_[i] == 1 && j != -lim) dp[op][j + DT] += dp[op ^ 1][j - 1 + DT] + abs(j) + abs(j - 1) * (d[i] - 1);
// else if(op_[i] == 2)
// {
// dp[op][j + DT] += dp[op ^ 1][j + DT] + abs(j);
// if(j != lim) dp[op][j + DT] += dp[op ^ 1][j + 1 + DT] + abs(j) + abs(j + 1) * (d[i] - 1);
// }
// }
// }
// return dp[op][mid + DT].mn;
pos = mid, base = 0, val = 1;
ql.clear(), qr.clear();
auto out = [&]() -> void
{
printf("ql : "); for(pii x : ql) printf("[%d %d] ", x.fi, x.se); putc('\n');
printf("pos = %d, base = %d, val = %d\n", pos, base, val);
printf("qr : "); for(pii x : qr) printf("[%d %d] ", x.fi, x.se); putc('\n');
};
for(int i = 1; i <= n; i++)
{
auto flush = [&](int v) -> void
{
// while(pos > 0 && !ql.empty() && ql.back().fi <= v)
// {
// base += ql.back().fi * abs(pos);
// v -= ql.back().fi;
// --pos;
// qr.push_front(mkp(0, val));
// val = ql.back().se;
// ql.pop_back();
// }
// while(pos < 0 && !qr.empty() && qr.front().fi <= v)
// {
// base += qr.front().fi * abs(pos);
// v -= qr.front().fi;
// ++pos;
// ql.push_back(mkp(0, val));
// val = qr.front().se;
// qr.pop_front();
// }
while(pos > 0 && v)
{
int t = v;
if(!ql.empty()) ckmin(t, ql.back().fi);
v -= t;
base += pos * t;
int len = ql.size();
if(0 <= pos - len)
{
if(!ql.empty()) ql.back().fi -= t;
if(!qr.empty()) qr.front().fi += t;
}
else
{
ql.back().fi -= t;
ql[len - pos - 1].fi += 2 * t;
if(!qr.empty()) qr.front().fi += t;
}
if(!ql.empty() && ql.back().fi == 0)
{
pos--;
qr.push_front(mkp(0, val));
val = ql.back().se;
ql.pop_back();
}
}
while(pos < 0 && v)
{
int t = v;
if(!qr.empty()) ckmin(t, qr.front().fi);
v -= t;
base -= pos * t;
int len = qr.size();
if(pos + len <= 0)
{
if(!qr.empty()) qr.front().fi -= t;
if(!ql.empty()) ql.back().fi += t;
}
else
{
qr.front().fi -= t;
qr[-pos].fi += 2 * t;
if(!ql.empty()) ql.back().fi += t;
}
if(!qr.empty() && qr.front().fi == 0)
{
pos++;
ql.push_back(mkp(0, val));
val = qr.front().se;
qr.pop_front();
}
}
if(pos == 0)
{
if(!ql.empty()) ql.back().fi += v;
if(!qr.empty()) qr.front().fi += v;
}
// else if(0 < pos)
// {
// base += pos * v;
// int len = ql.size();
// if(0 <= pos - len)
// {
// if(!ql.empty()) ql.back().fi -= v;
// if(!qr.empty()) qr.front().fi += v;
// }
// else
// {
// ql.back().fi -= v;
// ql[len - pos - 1].fi += 2 * v;
// if(!qr.empty()) qr.front().fi += v;
// }
// }
// else if(pos < 0)
// {
// base -= pos * v;
// int len = qr.size();
// if(pos + len <= 0)
// {
// if(!qr.empty()) qr.front().fi -= v;
// if(!ql.empty()) ql.back().fi += v;
// }
// else
// {
// qr.front().fi -= v;
// qr[-pos].fi += 2 * v;
// if(!ql.empty()) ql.back().fi += v;
// }
// }
};
auto moveright = [&]() -> void
{
pos++;
};
auto moveleft = [&]() -> void
{
top = 0;
while(!ql.empty() && !ql.back().fi) sta[++top] = ql.back().se, ql.pop_back();
std::sort(sta + 1, sta + 1 + top);
sta[++top] = val;
pos -= top;
while(!qr.empty() && !qr.front().fi) sta[++top] = qr.front().se, qr.pop_front();
sta[0] = 0;
for(int i = 1; i <= top; i++) plus_(sta[i - 1], sta[i]);
for(int i = top; i >= 1; i--) qr.push_front(mkp(0, sta[i]));
val = sta[0];
};
flush(d[i] - 1);
// printf("i = %d, flush(%d)\n", i, d[i] - 1), out();
if(op_[i] == 1) moveright();//, printf("moveright\n"), out();
if(op_[i] == 2) moveleft();//, printf("moveleft\n"), out();
flush(1);
// printf("flush(1)\n"), out();
}
// out();
int dt = 0;
while(pos < mid)
{
if(qr.empty()) debug("???\n");
++pos;
dt += qr.front().fi;
base += dt;
ql.push_back(mkp(-qr.front().fi, val));
val = qr.front().se;
qr.pop_front();
}
while(mid < pos)
{
if(ql.empty()) debug("???\n");
--pos;
dt += ql.back().fi;
base += dt;
qr.push_front(mkp(-ql.back().fi, val));
val = ql.back().se;
ql.pop_back();
}
while(!ql.empty() && !ql.back().fi) plus_(val, ql.back().se), ql.pop_back();
while(!qr.empty() && !qr.front().fi) plus_(val, qr.front().se), qr.pop_back();
// out();
// printf("return [%d %d]\n", base, val);
// exit(1);
return base;
}
void solve()
{
// memset(h, idx = -1, sizeof(h));
m = read(), A = read(), B = read(), n = A + B;
for(int i = 1; i <= n; i++)
{
x_[i] = read(); readstr(s, 0);
op_[i] = (s[0] == 'P' ? 1 : 2);
}
// printf("x[%d] = %d, m = %d\n", n, x_[n], m);
x_[0] = x_[n] - m;
for(int i = 1; i <= n; i++) d[i] = x_[i] - x_[i - 1];
pii res = mkp(calc(n), n);
for(int l = -n, r = n, mid, lx, rx; l <= r; )
{
mid = (l + r) >> 1;
lx = calc(mid);
rx = calc(mid + 1);
ckmin(res, mkp(lx, mid));
ckmin(res, mkp(rx, mid + 1));
if(lx <= rx) r = mid - 1;
else l = mid + 1;
}
int ans = 0;
print(res.fi, '\n');
calc(res.se); ans = val;
if(res.fi == calc(res.se - 1)) plus_(ans, val);
if(res.fi == calc(res.se + 1)) plus_(ans, val);
print(ans, '\n');
}
void init()
{
}
char _ED_;
void mian()
{
debug("%.3f MB\n", abs(&_ST_ - &_ED_) / 1024.0 / 1024);
init(); int T = 1;
for(; T; solve(), T--);
}
#ifdef int
#undef int
#endif
}
int main()
{
uvu::mian(); return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 14028kb
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: 14160kb
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: 332ms
memory: 21584kb
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: 354ms
memory: 21524kb
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: 291ms
memory: 21616kb
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: 373ms
memory: 21652kb
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: 242ms
memory: 21704kb
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: 196ms
memory: 18600kb
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: 196ms
memory: 18472kb
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: 252ms
memory: 19620kb
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: 297ms
memory: 19540kb
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: 296ms
memory: 21720kb
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: 203ms
memory: 20708kb
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: -100
Wrong Answer
time: 362ms
memory: 21196kb
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 758621014
result:
wrong answer 2nd lines differ - expected: '930867409', found: '758621014'