QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#225798#5466. Permutation CompressionZSH_ZSH#WA 1ms8128kbC++142.4kb2023-10-25 09:22:172023-10-25 09:22:18

Judging History

你现在查看的是最新测评结果

  • [2023-10-25 09:22:18]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8128kb
  • [2023-10-25 09:22:17]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for (register int i=(a);i<=(b);i++)
#define drep(i,a,b) for (register int i=(a);i>=(b);i--)
typedef long long ll;
using namespace std;

const int N=200010;

int n,a[N],b[N],pos[N],m,K;

#define mid ((start+end)>>1)
namespace SMT
{
	int mx[N<<2];
	inline void push_up(int node)
	{
		mx[node]=max(mx[node<<1],mx[node<<1|1]);
	}
	void build(int node,int start,int end)
	{
		if (start==end)
		{
			mx[node]=a[start];
			return;
		}
		build(node<<1,start,mid);
		build(node<<1|1,mid+1,end);
		push_up(node);
	} 
	void update(int node,int start,int end,int id,int v)
	{
		if (start==end)
		{
			mx[node]=v;
			return;
		}
		if (id<=mid) update(node<<1,start,mid,id,v);
		else update(node<<1|1,mid+1,end,id,v);
	}
	int q(int node,int start,int end,int L,int R)
	{
		if (start>R||end<L) return 0;
		if (start>=L&&end<=R) return mx[node];
		return max(q(node<<1,start,mid,L,R),q(node<<1|1,mid+1,end,L,R));
	}
}
#undef mid

struct BIT
{
	int t[N];
	void clear(int n)
	{
		memset(t,0,sizeof(int)*(n+5));
	}
	void update(int x,int v)
	{
		while (x<=n) t[x]+=v,x+=(x&(-x));
	}
	int getsum(int x)
	{
		int res=0;
		while (x) res+=t[x],x-=(x&(-x));
		return res;
	}
	int q(int l,int r)
	{
		if (l>r) return 0;
		return getsum(r)-getsum(l-1); 
	}
}bit;

void solve()
{
	cin>>n>>m>>K;
	rep(i,1,n) cin>>a[i];
	rep(i,1,m) cin>>b[i];
	
	multiset<int> S;
	rep(i,1,K)
	{
		int x; cin>>x;
		S.insert(x);
	}
	
	rep(i,1,n) pos[a[i]]=i;
	rep(i,1,m-1) if (pos[b[i]]>pos[b[i+1]])
	{
		printf("NO\n");
		return;
	}
	
	vector<int> vis(n+1),vec;
	rep(i,1,m) vis[b[i]]=1;
	rep(i,1,n) if (!vis[i]) vec.push_back(i);
	reverse(vec.begin(),vec.end());
	SMT::build(1,1,n);
	bit.clear(n);
	
	for (auto x:vec)
	{
		int p=pos[x],L,R;
		{
			int l=1,r=p;
			while (l<r)
			{
				int mid=(l+r)>>1;
				if (SMT::q(1,1,n,mid,p)==x) r=mid;
				else l=mid+1;
			}
			L=l;
		}
		{
			int l=p,r=n;
			while (l<r)
			{
				int mid=(l+r)>>1;
				if (SMT::q(1,1,n,p,mid+1)==x) l=mid+1;
				else r=mid;
			}
			R=l;
		}
		
		int len=R-L+1-bit.q(L,R);
		if (!S.size()||*(S.begin())>len)
		{
			printf("NO\n");
			return;
		}
		
		bit.update(p,1);
		SMT::update(1,1,n,p,0);
		auto it=prev(S.upper_bound(len));
		S.erase(it);
	}
	printf("YES\n");
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	
	int T; cin>>T;
	while (T--) solve();
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 8128kb

input:

3
5 2 3
5 1 3 2 4
5 2
1 2 4
5 5 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
3 2 2
3 1 2
3 2
2 3

output:

YES
YES
NO

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 8064kb

input:

100
2 1 2
2 1
2
1 1
2 1 2
1 2
1
2 2
2 1 1
1 2
1
2
6 1 5
3 4 2 5 6 1
3
5 2 1 1 1
6 1 6
2 1 3 6 4 5
1
4 1 2 2 1 4
3 3 2
2 1 3
2 1 3
2 2
1 1 1
1
1
1
1 1 1
1
1
1
2 1 2
2 1
2
1 2
4 4 3
2 1 3 4
2 1 3 4
4 3 1
1 1 1
1
1
1
6 5 1
6 2 5 4 3 1
6 2 4 3 1
4
1 1 1
1
1
1
6 5 3
3 6 1 4 5 2
3 6 1 4 2
3 3 4
4 3 4
3 4 ...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YE...

result:

wrong answer 82nd lines differ - expected: 'YES', found: 'NO'