QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#212769 | #5459. Goose, goose, DUCK? | Emolga | TL | 0ms | 0kb | C++14 | 2.2kb | 2023-10-13 20:27:06 | 2023-10-13 20:27:07 |
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;
}
詳細信息
Test #1:
score: 0
Time Limit Exceeded
input:
6 2 1 2 2 1 3 3