QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#381669 | #5466. Permutation Compression | wsc2008 | WA | 1ms | 3920kb | C++14 | 1.8kb | 2024-04-07 20:01:24 | 2024-04-07 20:01:25 |
Judging History
answer
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void write(ll x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
}
const ll N=1e6+9;
ll T,n,m,k,a[N],b[N],len[N],pa[N],pb[N],bit[N];
void Upd(ll x,ll k){
while(x<=n)bit[x]+=k,x+=(x&(-x));
}
ll Query(ll x){
ll res=0;
while(x)res+=bit[x],x-=(x&(-x));
return res;
}
ll Query(ll l,ll r){
return Query(r)-Query(l-1);
}
void solve(){
n=read(),m=read(),k=read();
rep(i,0,n+1)pa[i]=pb[i]=bit[i]=0;
rep(i,1,n)a[i]=read(),pa[a[i]]=i;
rep(i,1,m)b[i]=read(),pb[b[i]]=i;
rep(i,1,k)len[i]=read();
//判断是不是子序列
rep(i,1,m-1){
if(pa[b[i]]>pa[b[i+1]])return puts("NO"),void();
}
set<ll>A,B;
//A 维护删除了 >i 的所有数的情况
//B 维护还可选的 len 集合
rep(i,1,k)B.insert(len[i]);
rep(i,1,n)Upd(i,1);
A.insert(0),A.insert(n+1);
per(i,n,1){
if(pb[i])A.insert(pa[i]);
else {
ll l=*prev(A.lower_bound(pa[i])),r=*A.lower_bound(pa[i]);
ll cnt=Query(l+1,r-1);
set<ll>::iterator it=B.upper_bound(cnt);
if(it==B.begin())return puts("NO"),void();
B.erase(prev(it));
}
}
puts("YES");
}
bool Med;
int main(){
cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
T=read();
while(T--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3920kb
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: 3844kb
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 NO NO YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES NO YES YES YES YES NO YES YES YES YES YES NO NO YES YES YES NO NO NO NO YES NO NO YES YES YES YES YES NO YES NO YES NO YES NO YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES...
result:
wrong answer 4th lines differ - expected: 'YES', found: 'NO'