Submission #743836

#	Time	Username	Problem	Language	Result	Execution time	Memory
743836		zaneyu	Modern Machine (JOI23_ho_t5)	C++17	37 / 100	803 ms	77352 KiB

Main

#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);
}
signed 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,m-1,l,r);
		cout<<cur<<'\n';
	}
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 12
• Subtask 3: 0 / 10
• Subtask 4: 11 / 11
• Subtask 5: 26 / 26
• Subtask 6: 0 / 17
• Subtask 7: 0 / 21