oj.uz

Submission #743836

# Submission time Handle Problem Language Result Execution time Memory
743836 2023-05-18T04:39:47 Z zaneyu Modern Machine (JOI23_ho_t5) C++17
37 / 100
 803 ms 77352 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(){
	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.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 19112 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 19112 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 19112 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 326 ms 36744 KB Output is correct
3 Correct 296 ms 38196 KB Output is correct
4 Correct 176 ms 29024 KB Output is correct
5 Correct 148 ms 37568 KB Output is correct
6 Correct 153 ms 38184 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 326 ms 36744 KB Output is correct
3 Correct 296 ms 38196 KB Output is correct
4 Correct 176 ms 29024 KB Output is correct
5 Correct 148 ms 37568 KB Output is correct
6 Correct 153 ms 38184 KB Output is correct
7 Correct 11 ms 19028 KB Output is correct
8 Correct 13 ms 19028 KB Output is correct
9 Correct 11 ms 19028 KB Output is correct
10 Correct 16 ms 19844 KB Output is correct
11 Correct 757 ms 76884 KB Output is correct
12 Correct 803 ms 77352 KB Output is correct
13 Correct 402 ms 77060 KB Output is correct
14 Correct 455 ms 77108 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 326 ms 36744 KB Output is correct
3 Correct 296 ms 38196 KB Output is correct
4 Correct 176 ms 29024 KB Output is correct
5 Correct 148 ms 37568 KB Output is correct
6 Correct 153 ms 38184 KB Output is correct
7 Incorrect 10 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 19112 KB Output isn't correct
2 Halted 0 ms 0 KB -