oj.uz

Submission #743839

# Submission time Handle Problem Language Result Execution time Memory
743839 2023-05-18T04:44:16 Z zaneyu Modern Machine (JOI23_ho_t5) C++17
37 / 100
 1002 ms 76248 KB 
#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(){
	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.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 19028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 19028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 19028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 478 ms 36328 KB Output is correct
3 Correct 462 ms 36384 KB Output is correct
4 Correct 353 ms 27244 KB Output is correct
5 Correct 317 ms 36452 KB Output is correct
6 Correct 345 ms 36376 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 478 ms 36328 KB Output is correct
3 Correct 462 ms 36384 KB Output is correct
4 Correct 353 ms 27244 KB Output is correct
5 Correct 317 ms 36452 KB Output is correct
6 Correct 345 ms 36376 KB Output is correct
7 Correct 11 ms 19064 KB Output is correct
8 Correct 10 ms 19088 KB Output is correct
9 Correct 12 ms 19124 KB Output is correct
10 Correct 14 ms 19764 KB Output is correct
11 Correct 973 ms 76248 KB Output is correct
12 Correct 1002 ms 75616 KB Output is correct
13 Correct 567 ms 76156 KB Output is correct
14 Correct 642 ms 76152 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 478 ms 36328 KB Output is correct
3 Correct 462 ms 36384 KB Output is correct
4 Correct 353 ms 27244 KB Output is correct
5 Correct 317 ms 36452 KB Output is correct
6 Correct 345 ms 36376 KB Output is correct
7 Incorrect 11 ms 19028 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 19028 KB Output isn't correct
2 Halted 0 ms 0 KB -