QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#882945#8772. House DeconstructionningagoWA 388ms21808kbC++148.8kb2025-02-05 13:47:452025-02-05 13:47:46

Judging History

This is the latest submission verdict.

  • [2025-02-05 13:47:46]
  • Judged
  • Verdict: WA
  • Time: 388ms
  • Memory: 21808kb
  • [2025-02-05 13:47:45]
  • Submitted

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::reverse(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_front();
	// 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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 14156kb

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: 14156kb

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: 340ms
memory: 19592kb

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: 359ms
memory: 21652kb

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: 266ms
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: 388ms
memory: 21648kb

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: 255ms
memory: 19672kb

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: 202ms
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: 201ms
memory: 18664kb

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: 261ms
memory: 21808kb

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: 302ms
memory: 21716kb

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: 307ms
memory: 19624kb

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: 216ms
memory: 20836kb

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: 368ms
memory: 19156kb

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
863490465

result:

wrong answer 2nd lines differ - expected: '930867409', found: '863490465'