Submission #1253171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253171		iuvt	Gift Exchange (JOI24_ho_t4)	C++20	10 / 100	47 ms	47176 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int N=5e5+5;
struct tree_mx{
	static constexpr int YU=N*2;
	static int lowbit(const int x){
		return x&(-x);
	}
	int a[YU];
	void clear(){
		for(int &x:a){
			x=-1e9;
		}
	}
	tree_mx(){
		clear();
	}
	void update(const int w,const int p){
		for(int i=w;i>=1;i-=lowbit(i)){
			a[i]=max(a[i],p);
		}
	}
	int query(const int l)const{
		int ans=-1e9;
		for(int i=l;i<YU;i+=lowbit(i)){
			ans=max(ans,a[i]);
		}
		return ans;
	}
}tr_mx;
struct tree_he{
	static constexpr int YU=N;
	static int lowbit(const int x){
		return x&(-x);
	}
	int a[YU];
	void update(const int l,const int r){
		for(int i=r;i>=1;i-=lowbit(i)){
			++a[i];
		}
		for(int i=l-1;i>=1;i-=lowbit(i)){
			--a[i];
		}
	}
	void update_(const int l,const int r){
		for(int i=r;i>=1;i-=lowbit(i)){
			--a[i];
		}
		for(int i=l-1;i>=1;i-=lowbit(i)){
			++a[i];
		}
	}
	int query(const int l)const{
		int ans=0;
		for(int i=l;i<YU;i+=lowbit(i)){
			ans+=a[i];
		}
		return ans;
	}
}tr_he;
int n,m;
int a[N],b[N];
int l[N],r[N];
vector<pair<int,int>> bx[N],xx[N];
void get_lr(){
	for(int i=1;i<=n;++i){
		l[i]=tr_mx.query(b[i]);
		tr_mx.update(a[i],i);
	}
	tr_mx.clear();
	for(int i=n;i>=1;--i){
		r[i]=-tr_mx.query(b[i]);
		tr_mx.update(a[i],-i);
	}
	for(int i=1;i<=n;++i){
		l[i]=max(l[i],0);
		r[i]=min(r[i],n+1);
		bx[i].emplace_back(l[i]+1,i);
		xx[r[i]].emplace_back(l[i]+1,i);
	}
}
struct quer{
	int l,id;
};
vector<quer>q[N];
int ans[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	for(int i=1;i<=n;++i){
		cin>>b[i];
	}
	cin>>m;
	for(int i=1;i<=m;++i){
		int wl,wr;
		cin>>wl>>wr;
		q[wr].push_back({wl,i});
	}
	get_lr();
	for(int i=1;i<=n;++i){
		for(const auto &x:bx[i]){
			tr_he.update(x.first,x.second);
		}
		for(const auto &x:xx[i]){
			tr_he.update_(x.first,x.second);
		}
		for(const auto&x:q[i]){
			ans[x.id]=tr_he.query(x.l);
		}
	}
	for(int i=1;i<=m;++i){
		cout<<(ans[i]?"No":"Yes")<<'\n';
	}
	return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 10 / 10
• Subtask 4: 0 / 31
• Subtask 5: 0 / 8
• Subtask 6: 0 / 12
• Subtask 7: 0 / 18
• Subtask 8: 0 / 12