Submission #734830

#	Time	Username	Problem	Language	Result	Execution time	Memory
734830		lucri	Linear Garden (IOI08_linear_garden)	C++17	100 / 100	95 ms	25824 KiB

linear_garden

#include <bits/stdc++.h>
using namespace std;
long long n,m,pd[1000010][3],poza,sum,ans;
char s[1000010];
void RezolvaRange(long long b,long long e)
{
    sum=0;
    for(long long i=1;i<=n;++i)
    {
        if(s[i-1]=='L')
            --sum;
        else if(s[i-1]=='P')
            ++sum;
        if(sum<b||sum>e)
            sum=1000000000000000000;
        pd[i][0]=pd[i][1]=pd[i][2]=0;
        if(sum<=e&&sum>=b+1&&s[i]=='P')
            ++pd[i][sum-b-1];
        pd[i][0]+=pd[i-1][1];
        pd[i][1]+=pd[i-1][0]+pd[i-1][2];
        if(e-b>=2)
            pd[i][2]+=pd[i-1][1];
        pd[i][0]%=m;
        pd[i][1]%=m;
        pd[i][2]%=m;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>s+1;
    ans=1;
    RezolvaRange(-2,0);
    ans+=pd[n][0];
    ans+=pd[n][1];
    ans+=pd[n][2];
    RezolvaRange(-1,1);
    ans+=pd[n][0];
    ans+=pd[n][1];
    ans+=pd[n][2];
    RezolvaRange(0,2);
    ans+=pd[n][0];
    ans+=pd[n][1];
    ans+=pd[n][2];
    RezolvaRange(-1,0);
    ans-=pd[n][0];
    ans-=pd[n][1];
    RezolvaRange(0,1);
    ans-=pd[n][0];
    ans-=pd[n][1];
    cout<<(ans%m+m)%m;
    return 0;
}

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:33:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |     cin>>n>>m>>s+1;
      |                ~^~

• 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: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5
• Subtask 22: 5 / 5
• Subtask 23: 5 / 5