Submission #1178973

#TimeUsernameProblemLanguageResultExecution timeMemory
1178973vicvicLinear Garden (IOI08_linear_garden)C++20
80 / 100
13 ms9184 KiB
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <cstdint> #define int long long using namespace std; const int NMAX=1e6; int n, mod, e[NMAX+5]; string s; int ans=1; int32_t main () { ios :: sync_with_stdio (0); cin.tie (nullptr); cin >> n >> mod >> s; e[0]=1; for (int i=1;i<=n;i++) { e[i]=2*(e[i-1])%mod; } int mx=0, mn=0, crt=0; for (int i=0;i<n;i++) { int len=n-i-1; if (s[i]=='P') { int temp_mx=max (mx, crt+1); if (temp_mx-mn==2) { if (temp_mx==1) { ans=ans+e[(len+1)/2]; ans%=mod; } else { ans=ans+e[len/2]; ans%=mod; } } else if (temp_mx-mn==1) { ans=ans+e[(len+1)/2]+e[(len)/2]-1; ans%=mod; } mn=min (mn, --crt); } else mx=max (mx, ++crt); } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...