QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#212748	#5466. Permutation Compression	zzzyzzz^#	WA	1ms	9964kb	C++17	2.2kb	2023-10-13 20:19:11	2023-10-13 20:19:11

Judging History

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

[2023-10-13 20:19:11]
评测

测评结果：WA
用时：1ms
内存：9964kb

查看

[2023-10-13 20:19:11]
提交

answer

#include<bits/stdc++.h>
#include<sstream>
#include<cassert>
#define fi first
#define se second
#define i128 __int128
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> PII;
const double eps=1e-7;
const int N=5e5+7 ,M=5e5+7, INF=0x3f3f3f3f,mod=1e9+7,mod1=998244353;
const long long int llINF=0x3f3f3f3f3f3f3f3f;
inline ll read() {ll x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=(ll)x*10+c-'0';c=getchar();} return x*f;}
inline void write(ll x) {if(x < 0) {putchar('-'); x = -x;}if(x >= 10) write(x / 10);putchar(x % 10 + '0');}
inline void write(ll x,char ch) {write(x);putchar(ch);}
void stin() {freopen("in_put.txt","r",stdin);freopen("my_out_put.txt","w",stdout);}
bool cmp0(int a,int b) {return a>b;}
template<typename T> T gcd(T a,T b) {return b==0?a:gcd(b,a%b);}
template<typename T> T lcm(T a,T b) {return a*b/gcd(a,b);}
void hack() {printf("\n----------------------------------\n");}

int T,hackT;
int n,m,k;
int w[N];
bool b[N];
int l[N],r[N];
int stk[N],top;

void solve() {
	n=read(),m=read(),k=read();
	
	for(int i=1;i<=n;i++) w[i]=read(),b[i]=false;
	for(int i=1;i<=m;i++) b[read()]=true;
	
	multiset<int> s;
	for(int i=1;i<=k;i++) {
		int c=read();
		s.insert(-c);
	}
	
	if(n-m>k) printf("NO\n");
	else {
		stk[0]=0,top=0;
		for(int i=1;i<=n;i++) {
			while(top&&w[stk[top]]<=w[i]) top--;
			l[i]=stk[top];
			stk[++top]=i;
		}	
		stk[0]=n+1,top=0;
		for(int i=n;i>=1;i--) {
			while(top&&w[stk[top]]<=w[i]) top--;
			r[i]=stk[top];
			stk[++top]=i;
		}
		
		vector<int> vis;
		
		bool flag=true;
		for(int i=1;i<=n;i++) {
			if(b[w[i]]) continue;
			int vp=(r[i]-1)-(l[i]+1)+1;
			vis.push_back(vp);
		}
		
		sort(vis.begin(),vis.end());
		for(auto &it:vis) {
			auto vi=s.lower_bound(-it);
			if(vi==s.end()) {
				flag=false;
				break;
			}else {
				s.erase(vi);
			}
		}
		
		if(!flag) printf("NO\n");
		else printf("YES\n");
	}
}   

int main() {
    // init();
    // stin();
	// ios::sync_with_stdio(false); 

    scanf("%d",&T);
    // T=1; 
    while(T--) hackT++,solve();
    
    return 0;       
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 9964kb

input:

output:

YES
YES
NO

result:

ok 3 lines

Test #2:

score: -100

Wrong Answer

time: 1ms

memory: 9964kb

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

result:

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