Submission #937999

#TimeUsernameProblemLanguageResultExecution timeMemory
937999kimLinear Garden (IOI08_linear_garden)C++17
100 / 100
16 ms10508 KiB
#include<bits/stdc++.h> using namespace std; using ll=long long; int n,m,qs[1000005],cnt[5],pw[1000005]={1}; string s; int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m>>s; set<int> Set; Set.insert(0); cnt[2]=1; for(int i=1;i<=n;++i){ pw[i]=(pw[i-1]<<1)%m; qs[i]=qs[i-1]+(s[i-1]=='L'?-1:1); if(!cnt[qs[i]+2]++) Set.insert(qs[i]); } ll ans=1; for(int i=n;i>0;--i){ if(--cnt[qs[i]+2]==0) Set.erase(qs[i]); int mn=*Set.rbegin()-2; int mx=*Set.begin()+2; if(s[i-1]=='L') continue; bool a=qs[i]-4>=mn&&qs[i]-2<=mx; bool b=qs[i]-3>=mn&&qs[i]-1<=mx; bool c=qs[i]-2>=mn&&qs[i]<=mx; ans=(ans+(a+c)*pw[n-i>>1])%m; if(b){ ans=(ans+(a+c)*(m-1))%m; ans=(ans+pw[n-i+1>>1])%m; } } cout<<ans; return 0; }

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:30:28: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   30 |         ans=(ans+(a+c)*pw[n-i>>1])%m;
      |                           ~^~
linear_garden.cpp:33:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |             ans=(ans+pw[n-i+1>>1])%m;
      |                         ~~~^~
#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...