이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h> //:3
using namespace std;
typedef long long LL;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define sz(x) (int)((x).size())
#define int long long
/*
#define cin in
#define cout out
ifstream in("leftmax.in");
ofstream out("leftmax.out");
*/
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const LL inf = 2e9;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int N = 2e6 + 11;
const LL INF64 = 3e18 + 1;
const double eps = 1e-14;
const double PI = acos(-1);
int n, m, k, M, P[N];
void solve(){
cin >> n >> M;
string s;
cin >> s;
P[0] = 1;
for(int i = 1; i <= n; i++){
P[i] = (P[i - 1] * 2) % M;
}
int sum = 0, mx = 0, mn = 0, ans = 0;
for(int i = 0; i < sz(s); i++){
if(s[i] == 'L'){
mx = max(mx, ++sum);
continue;
}
int MX = max(mx, sum + 1), MN = mn, SUM = sum + 1, k = n - i - 1;
sum--;
mn = min(mn, sum);
if(MX - MN > 2)continue;
if(MX - MN == 2){
if(MN < SUM && SUM < MX){
ans = (ans + P[(k + 1) >> 1]) % M;
}else ans = (ans + P[k >> 1]) % M;
}else{
ans = (ans + P[(k + 1) >> 1] + P[k >> 1] - 1) % M;
}
}
cout << (ans + M + 1) % M << '\n';
}
int32_t main(){
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
//cout << setprecision(6) << fixed;
int T = 1;
//cin >> T;
while(T--){
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |