QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#430438 | #8772. House Deconstruction | Kevin5307 | RE | 0ms | 3716kb | C++23 | 2.3kb | 2024-06-03 20:20:38 | 2024-06-03 20:20:39 |
Judging History
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[200200];
char type[200200];
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3592kb
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: 3716kb
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
Runtime Error
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...