QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#430506 | #8772. House Deconstruction | Kevin5307 | RE | 507ms | 26580kb | C++23 | 2.9kb | 2024-06-03 21:33:15 | 2024-06-03 21:33:16 |
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[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;
int layer=0;
while(L<R)
{
assert(++layer<=50);
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: 18144kb
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: 7ms
memory: 17916kb
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: 507ms
memory: 26580kb
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
Runtime Error
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...