Submission #372569

#	Time	Username	Problem	Language	Result	Execution time	Memory
372569		Hehehe	Linear Garden (IOI08_linear_garden)	C++14	75 / 100	11 ms	7580 KiB

linear_garden

#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 = 2e5 + 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;

    n = sz(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();
    }
}

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 4 / 4
• Subtask 7: 4 / 4
• Subtask 8: 4 / 4
• Subtask 9: 4 / 4
• Subtask 10: 4 / 4
• Subtask 11: 4 / 4
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5