QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#381670 | #5466. Permutation Compression | wsc2008 | WA | 2ms | 14168kb | C++14 | 1.8kb | 2024-04-07 20:02:07 | 2024-04-07 20:02:07 |
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();
}
multiset<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: 0ms
memory: 14168kb
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: 2ms
memory: 14092kb
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 YES YES YES YES YES YES YES YES YES YES YES NO NO NO YES YES YES NO YES YES YES YES YES 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 YE...
result:
wrong answer 28th lines differ - expected: 'NO', found: 'YES'