#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll maxn=2e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-4;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define pp pair<pii,int>
vector<pp> seg[4*maxn];
int arr[maxn];
int n,m;
int md;
pp mt(int a,int b,int c){
return make_pair(make_pair(a,b),c);
}
vector<pp> mrg(vector<pp> a,vector<pp> b){
vector<pp> res;
for(auto x:a){
int nw=(x.f.f+x.s)%md,n2=(x.f.s+x.s)%md;
int p=lower_bound(ALL(b),mt(nw+1,0,0))-b.begin()-1,p2=lower_bound(ALL(b),mt(n2+1,0,0))-b.begin()-1;
if(nw>n2) p2+=sz(b);
for(int j=p;j<=p2;j++){
int z=(j%sz(b));
int cl=nw,cr=n2;
if(cl>cr){
if(j>=sz(b)) cl=0;
else cr=md-1;
}
MXTO(cl,b[z].f.f);
MNTO(cr,b[z].f.s);
res.pb({{(cl-x.s+md)%md,(cr-x.s+md)%md},(x.s+b[z].s)%md});
}
}
/*for(auto x:res){
cout<<x.f.f<<' '<<x.f.s<<'\n';
}*/
return res;
}
void build(int idx,int l,int r){
if(l==r){
seg[idx].pb({{0,arr[l]-1},arr[l]+1});
seg[idx].pb({{arr[l],md-1},arr[l]});
return;
}
int mid=(l+r)/2;
build(idx*2,l,mid);
build(idx*2+1,mid+1,r);
seg[idx]=mrg(seg[idx*2],seg[idx*2+1]);
}
int cur=0;
void query(int idx,int l,int r,int ql,int qr){
if(r<ql or l>qr) return;
if(ql<=l and r<=qr){
int p=lower_bound(ALL(seg[idx]),mt(cur+1,0,0))-seg[idx].begin()-1;
cur+=seg[idx][p].s;
cur%=md;
return;
}
int mid=(l+r)/2;
query(idx*2,l,mid,ql,qr),query(idx*2+1,mid+1,r,ql,qr);
}
int main(){
ios::sync_with_stdio(false),cin.tie(0);
cin>>n>>m;
md=(n+1);
string s;
cin>>s;
int t=0;
REP(i,n){
if(s[i]=='R') t=i+1;
}
REP(i,m) cin>>arr[i];
build(1,0,m-1);
int q;
cin>>q;
REP(i,q){
cur=t;
int l,r;
cin>>l>>r;
--l,--r;
query(1,0,n-1,l,r);
cout<<cur<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
38476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
38476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
38476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
19116 KB |
Output is correct |
| 2 |
Incorrect |
125 ms |
38212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
19116 KB |
Output is correct |
| 2 |
Incorrect |
125 ms |
38212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
19116 KB |
Output is correct |
| 2 |
Incorrect |
125 ms |
38212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
38476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
