QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#430516#8772. House DeconstructionKevin5307AC ✓485ms26536kbC++232.9kb2024-06-03 21:36:122024-06-03 21:36:12

Judging History

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

  • [2024-06-03 21:36:12]
  • 评测
  • 测评结果:AC
  • 用时:485ms
  • 内存:26536kb
  • [2024-06-03 21:36:12]
  • 提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
const ll mod=998244353;
ll x;
int n,m;
ll pos[400400];
char type[400400];
bool used[400400];
ll dp[400400],cnt[400400];
int psum[400400];
int nxt[400400];
int ppos[800800];
ll psum2[400400];
inline ll red(ll x){return x>=mod?x-mod:x;}
ll calc(ll k,bool tp)
{
	for(int i=1;i<=n+m;i++)
		used[i]=0;
	ll sum=0;
	int tmp1=max(k,0ll),tmp2=max(-k,0ll);
	for(int i=1;i<=n+m;i++)
	{
		if(tmp1&&type[i]=='P')
		{
			tmp1--;
			sum+=pos[i];
			used[i]=1;
		}
		if(tmp2&&type[i]=='H')
		{
			tmp2--;
			sum+=pos[i];
			used[i]=1;
		}
	}
	tmp1=max(k,0ll);
	tmp2=max(-k,0ll);
	for(int i=n+m;i>=1;i--)
	{
		if(tmp1&&type[i]=='H')
		{
			tmp1--;
			sum+=x-pos[i];
			used[i]=1;
		}
		if(tmp2&&type[i]=='P')
		{
			tmp2--;
			sum+=x-pos[i];
			used[i]=1;
		}
	}
	vector<int> vec;
	for(int i=1;i<=n+m;i++)
		if(!used[i])
			vec.pb(i);
	memset(dp,0x3f,sizeof(dp));
	memset(cnt,0,sizeof(cnt));
	memset(nxt,-1,sizeof(nxt));
	memset(ppos,-1,sizeof(ppos));
	dp[0]=0;
	cnt[0]=1;
	for(int i=0;i<sz(vec);i++)
		psum[i+1]=psum[i]+(type[vec[i]]=='P'?1:-1);
	for(int i=0;i<sz(vec);i++)
		psum2[i+1]=psum2[i]+(type[vec[i]]=='P'?pos[vec[i]]:-pos[vec[i]]);
	for(int i=sz(vec);i>=0;i--)
	{
		nxt[i]=ppos[psum[i]+400000];
		ppos[psum[i]+400000]=i;
	}
	for(int i=0;i<sz(vec);i++)
	{
		if(type[vec[i]]=='H')
		{
			if(dp[i]<dp[i+1])
			{
				dp[i+1]=dp[i];
				cnt[i+1]=0;
			}
			if(dp[i]==dp[i+1])
				cnt[i+1]=red(cnt[i]+cnt[i+1]);
		}
		if(nxt[i]!=-1)
		{
			if(dp[i]+abs(psum2[nxt[i]]-psum2[i])<dp[nxt[i]])
			{
				dp[nxt[i]]=dp[i]+abs(psum2[nxt[i]]-psum2[i]);
				cnt[nxt[i]]=0;
			}
			if(dp[i]+abs(psum2[nxt[i]]-psum2[i])==dp[nxt[i]])
				cnt[nxt[i]]=red(cnt[i]+cnt[nxt[i]]);
		}
	}
	if(!tp) return dp[sz(vec)]+sum;
	return cnt[sz(vec)];
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>x>>n>>m;
	for(int i=1;i<=n+m;i++)
		cin>>pos[i]>>type[i];
	ll L=-n,R=n;
	while(L<R)
	{
		ll Lmid=(int)(L+L+R+1+3e6)/3-1e6,Rmid=(int)(L+R+R+2+3e6)/3-1e6;
		ll Lval=calc(Lmid,0),Rval=calc(Rmid,0);
		if(Lval>=Rval)
			L=Lmid+1;
		else
			R=Rmid-1;
	}
	ll ans=0;
	ll Val=calc(L,0);
	for(int i=-2;i<=2;i++)
		if(calc(i+L,0)==Val)
			ans=(ans+calc(i+L,1))%mod;
	cout<<Val<<endl<<ans<<endl;
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 6ms
memory: 18140kb

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: 8ms
memory: 18140kb

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: 485ms
memory: 26532kb

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: 430ms
memory: 25684kb

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: 200ms
memory: 25056kb

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: 407ms
memory: 25712kb

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: 244ms
memory: 26332kb

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: 123ms
memory: 23684kb

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: 143ms
memory: 23884kb

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: 267ms
memory: 26356kb

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: 273ms
memory: 26536kb

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: 267ms
memory: 26316kb

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: 149ms
memory: 25476kb

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: 408ms
memory: 25500kb

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