Submission #1188757

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188757		mertbbm	Gift Exchange (JOI24_ho_t4)	C++20	100 / 100	1608 ms	223708 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<int,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

inline pii combine(const pii a, const pii b){
	return {min(a.first,b.first),max(a.second,b.second)};
}

struct node{
	int s,e,m;
	node *l,*r;
	pii v;
	bool lset;
	int lazySet;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v({1e15,0}),lset(0),lazySet(0){
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void self_set(int x){
		v.first=x;
		v.second=x;
		lset=1;
		lazySet=x;
	}
	
	void forceProp(){
		if(s==e) return;
		if(lset){
			l->self_set(lazySet);
			r->self_set(lazySet);
			lset=0;
			lazySet=0;
		}
	}
	
	void rangeSet(int x, int y, int c){
		if(x<=s&&y>=e){
			self_set(c);
			return;
		}
		forceProp();
		if(x<=m) l->rangeSet(x,y,c);
		if(y>m) r->rangeSet(x,y,c);
		v=combine(l->v,r->v);
	}
	
	pii query(int x, int y){
		if(x<=s&&y>=e){
			return v;
		}
		forceProp();
		if(y<=m) return l->query(x,y);
		if(x>m) return r->query(x,y);
		return combine(l->query(x,m),r->query(m+1,y));
	}
};

int fw[500005];

void upd(int x, int y){
	x++;
	while(x<500005){
		fw[x]+=y;
		x+=x&(-x);
	}
}

int sum(int x){
	x++;
	int counter=0;
	while(x>0){
		counter+=fw[x];
		x-=x&(-x);
	}
	return counter;
}

int query(int x, int y){
	return sum(y)-sum(x-1);
}

void solve(){
	int n;
	cin >> n;
	pii arr[n+5];
	for(int x=1;x<=n;x++) cin >> arr[x].second;
	for(int x=1;x<=n;x++) cin >> arr[x].first;
	
	int lft[n+5];
	int rgt[n+5];
	
	node st(0,2*n+5);
	for(int x=1;x<=n;x++){
		lft[x]=st.query(arr[x].first,arr[x].second).second;
		st.rangeSet(arr[x].first,arr[x].second,x);
	}
	
	st.rangeSet(0,2*n+5,n+1);
	vector<int>done[n+5];
	for(int x=n;x>=1;x--){
		rgt[x]=st.query(arr[x].first,arr[x].second).first;
		st.rangeSet(arr[x].first,arr[x].second,x);
		done[rgt[x]].push_back(x);
	}
	
	int q;
	int l,r;
	cin >> q;
	vector<pii>que[n+5];
	int ans[q];
	for(int x=0;x<q;x++){
		cin >> l >> r;
		que[r].push_back({l,x});
	}
	
	for(int x=1;x<=n;x++){
		upd(x,1);
		upd(lft[x],-1);
		for(auto it:done[x]){
			upd(it,-1);
			upd(lft[it],1);
		}
		
		for(auto it:que[x]){
			ans[it.second]=query(it.first,x);
		}
	}
	
	for(int x=0;x<q;x++){
		if(ans[x]) cout << "No\n";
		else cout << "Yes\n";
	}
}	
																   
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

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