QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#430441#8772. House DeconstructionKevin5307TL 0ms3568kbC++232.3kb2024-06-03 20:21:222024-06-03 20:21:22

Judging History

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

  • [2024-06-03 20:21:22]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3568kb
  • [2024-06-03 20:21:22]
  • 提交

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];
ll calc(ll k,bool tp)
{
	vector<ll> vDelta,vWays={1};
	ll stPos=k,stVal=0;
	ll lst=0;
	for(int i=1;i<=n+m;i++)
	{
		ll cnt=pos[i]-lst-1;
		for(int j=0;j<sz(vDelta);j++)
			if(j+stPos>=0)
				vDelta[j]+=cnt;
			else
				vDelta[j]-=cnt;
		stVal+=abs(stPos)*cnt;
		if(type[i]=='P')
		{
			stPos++;
			for(int j=0;j<sz(vDelta);j++)
				if(j+stPos>=0)
					vDelta[j]++;
				else
					vDelta[j]--;
			stVal+=abs(stPos);
		}
		else
		{
			stPos--;
			int pos=lb(vDelta,0);
			vDelta.insert(vDelta.begin()+pos,0);
			vWays.insert(vWays.begin()+pos,vWays[pos]);
			pos++;
			while(pos<sz(vDelta)&&vDelta[pos]==0)
			{
				vWays[pos]=(vWays[pos]+vWays[pos+1])%mod;
				pos++;
			}
			for(int j=0;j<sz(vDelta);j++)
				if(j+stPos>=0)
					vDelta[j]++;
				else
					vDelta[j]--;
			stVal+=abs(stPos);
		}
		lst=pos[i];
	}
	ll cnt=x-pos[n+m];
	for(int j=0;j<sz(vDelta);j++)
		if(j+stPos>=0)
			vDelta[j]+=cnt;
		else
			vDelta[j]-=cnt;
	stVal+=abs(stPos)*cnt;
	if(!tp)
	{
		ll sum=stVal;
		for(int i=0;i<sz(vDelta);i++)
			if(stPos+i<k)
				sum+=vDelta[i];
		return sum;
	}
	return vWays[k-stPos];
}
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=-1e6,R=1e6;
	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: 0ms
memory: 3568kb

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

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

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:


result: