QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#430505#8772. House DeconstructionKevin5307TL 479ms26532kbC++232.9kb2024-06-03 21:32:382024-06-03 21:32:39

Judging History

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

  • [2024-06-03 21:32:39]
  • 评测
  • 测评结果:TL
  • 用时:479ms
  • 内存:26532kb
  • [2024-06-03 21:32:38]
  • 提交

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=(L+L+R+1+3e6)/3-1e6,Rmid=(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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 17892kb

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: 5ms
memory: 20220kb

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: 479ms
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: -100
Time Limit Exceeded

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:


result: