oj.uz

Submission #743810

# Submission time Handle Problem Language Result Execution time Memory
743810 2023-05-18T03:27:02 Z zaneyu Modern Machine (JOI23_ho_t5) C++17
37 / 100
 808 ms 77892 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);
}
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,m-1,l,r);
		cout<<cur<<'\n';
	}
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 19008 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 19008 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 19008 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 11 ms 19008 KB Output is correct
2 Correct 256 ms 36380 KB Output is correct
3 Correct 287 ms 38004 KB Output is correct
4 Correct 148 ms 29004 KB Output is correct
5 Correct 141 ms 37528 KB Output is correct
6 Correct 160 ms 38176 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19008 KB Output is correct
2 Correct 256 ms 36380 KB Output is correct
3 Correct 287 ms 38004 KB Output is correct
4 Correct 148 ms 29004 KB Output is correct
5 Correct 141 ms 37528 KB Output is correct
6 Correct 160 ms 38176 KB Output is correct
7 Correct 12 ms 19028 KB Output is correct
8 Correct 11 ms 19156 KB Output is correct
9 Correct 10 ms 19028 KB Output is correct
10 Correct 13 ms 19796 KB Output is correct
11 Correct 731 ms 77440 KB Output is correct
12 Correct 808 ms 77892 KB Output is correct
13 Correct 354 ms 77112 KB Output is correct
14 Correct 426 ms 77488 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19008 KB Output is correct
2 Correct 256 ms 36380 KB Output is correct
3 Correct 287 ms 38004 KB Output is correct
4 Correct 148 ms 29004 KB Output is correct
5 Correct 141 ms 37528 KB Output is correct
6 Correct 160 ms 38176 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 19008 KB Output isn't correct
2 Halted 0 ms 0 KB -