QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#88982	#5466. Permutation Compression	Small_Black	WA	2ms	3404kb	C++14	1.9kb	2023-03-18 08:54:26	2023-03-18 08:54:29

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-03-18 08:54:29]
评测

测评结果：WA
用时：2ms
内存：3404kb

查看

[2023-03-18 08:54:26]
提交

answer

// Problem: L. Permutation Compression
// Contest: Codeforces - The 2023 ICPC Asia Hong Kong Regional Programming Contest (The 1st Universal Cup, Stage 2:Hong Kong)
// URL: https://codeforces.com/gym/104172/problem/L
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Date:2023-03-18 08:04:05
// By:SmallBlack
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
	long long s=0,k=1;
	char c=getchar();
	while(!isdigit(c))
	{
		k=(c=='-')?-1:1;
		c=getchar();
	}
	while(isdigit(c))
	{
		s=s*10+c-'0';
		c=getchar();
	}
	return s*k;
}
#define d read()
#define ll long long
#define Maxn 10010
#define Size 200010
#define mp make_pair
#define pb push_back
#define fi first
#define se second
ll c[Size],n;
inline ll low(ll x){return x&(-x);}
void add(ll a,ll x)
{
	for(;a<=n;a+=low(a))
		c[a]+=x;
}
ll query(ll y)
{
	ll ans=0;
	for(;y;y-=low(y))
		ans+=c[y];
	return ans;
}
ll a[Size],b[Size];
ll id[Size],cnt[Size];
ll skill[Size];
bool Del[Size];
vector<pair<ll,int> >check;
set<ll>pos;
bool solve()
{
	check.clear();
	n=d;
	ll m=d,k=d;
	for(int i=1;i<=n;i++)
		a[i]=d,id[a[i]]=i,Del[i]=cnt[i]=c[i]=0;
	for(int i=0;i<m;i++)
		b[i]=d,Del[b[i]]=1,check.pb(mp(id[b[i]],i));
	sort(check.begin(),check.end());
	for(int i=1;i<m;i++)
		if(check[i-1].se>check[i].se)
			return false;
	for(int i=0;i<k;i++)
		cnt[d]++;
	pos.clear(),pos.insert(0),pos.insert(n+1);
	for(int i=1;i<=n;i++) add(i,1);
	for(int i=n;i>=1;i--)
	{
		if(Del[i])
			pos.insert(id[i]);
		else
		{
			ll l=*(--pos.lower_bound(id[i]))+1,r=*pos.lower_bound(id[i])-1;
			cnt[query(r)-query(l-1)]--;
			add(id[i],-1);
		}
	}
	for(int i=1;i<=n;i++)
	{
		cnt[i]+=cnt[i-1];
		if(cnt[i]<0)
			return false;
	}
	return true;
}
int main()
{
	ll t=d;
	while(t--)
		if(solve()) puts("YES");
		else puts("NO");
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 3228kb

input:

output:

YES
YES
NO

result:

ok 3 lines

Test #2:

score: -100

Wrong Answer

time: 2ms

memory: 3404kb

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
NO
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
YES...

result:

wrong answer 46th lines differ - expected: 'YES', found: 'NO'