제출 #1284851

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284851		MuhammadSaram	Gift Exchange (JOI24_ho_t4)	C++20	100 / 100	1728 ms	74152 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define endl '\n'

const int M = 1e6 + 1;

int seg[M*2];

void modify(int p,int x,int v=0,int s=0,int e=M)
{
	if (s+1==e)
	{
		seg[v]=x;
		return;
	}
	int mid=(s+e)/2, lc=v+1, rc=v+(mid-s)*2;
	if (p<mid)
		modify(p,x,lc,s,mid);
	else
		modify(p,x,rc,mid,e);
	seg[v]=max(seg[lc],seg[rc]);
}

int get(int l,int r,int v=0,int s=0,int e=M)
{
	if (l>=e or r<=s) return -1;
	if (l<=s && e<=r) return seg[v];
	int mid=(s+e)/2, lc=v+1, rc=v+(mid-s)*2;
	return max(get(l,r,lc,s,mid),get(l,r,rc,mid,e));
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	
	int n;
	cin>>n;
	int a[n], b[n], ind[2*n+1], l[n], r[n];
	for (int i=0;i<n;i++)
		cin>>a[i],ind[a[i]]=i,l[i]=-1,r[i]=n;
	for (int i=0;i<n;i++)
		cin>>b[i],ind[b[i]]=i;
	set<int> se;
	for (int i=2*n;i>=1;i--)
	{
		if (se.count(ind[i]))
		{
			auto it=se.upper_bound(ind[i]);
			if (it!=se.end()) r[ind[i]]=*it;
			it=se.lower_bound(ind[i]);
			if (it!=se.begin()) it--,l[ind[i]]=*it;
			se.erase(ind[i]);
		}
		else
			se.insert(ind[i]);
	}
	for (int i=n-1;i>=0;i--)
	{
		int x=get(b[i],a[i]);
		r[i]=min(r[i],n-x);
		modify(a[i],n-i), modify(b[i],n-i);
	}
	for (int i=1;i<=2*n;i++) modify(i,-1);
	for (int i=0;i<n;i++)
	{
		int x=get(b[i],a[i]);
		l[i]=max(l[i],x);
		modify(a[i],i), modify(b[i],i);
	}
	vector<pair<int,int>> v[n];
	vector<int> v1[n];
	for (int i=0;i<n;i++)
	{
		modify(i,0);
		v1[l[i]+1].push_back(i);
	}
	int q;
	cin>>q;
	string ans[q];
	for (int i=0;i<q;i++)
	{
		int l,r;
		cin>>l>>r;
		v[l-1].push_back({r,i});
	}
	for (int l=0;l<n;l++)
	{
		for (int i:v1[l]) modify(i,r[i]);
		for (auto [r,i]:v[l])
		{
			if (get(l,r)<r) ans[i]="Yes";
			else ans[i]="No";
		}
	}
	for (int i=0;i<q;i++)
		cout<<ans[i]<<endl;
	
	return 0;
}

• 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