QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#249119 | #5466. Permutation Compression | joelgun14 | TL | 50ms | 10108kb | C++14 | 4.3kb | 2023-11-12 01:02:31 | 2023-11-12 01:02:31 |
Judging History
answer
#include <bits/stdc++.h>
#define vec vector
#define pb push_back
#define pii pair<int,int>
#define fs first
#define sc second
#define all(x) (x).begin(), (x).end()
#define ll long long
using namespace std;
const int LIM = 1<<18;
struct St {
vec<int> A;
int DEFAULT=0;
St() {
A.resize(LIM<<1, DEFAULT);
fill(all(A), DEFAULT);
}
int merge(int a, int b) {
return a+b;
}
void upd(int idx, int val) {
idx+=LIM;
A[idx]=val;
idx>>=1;
while (idx) {
A[idx]=merge(A[idx*2], A[idx*2+1]);
idx>>=1;
}
}
int query(int nd, int l, int r, int ql, int qr) {
if (ql<=l && r<=qr) return A[nd];
else if (ql>r || qr<l) return DEFAULT;
else {
int md=(l+r)/2;
return merge(query(nd*2, l, md, ql, qr), query(nd*2+1, md+1, r, ql, qr));
}
}
};
struct StMx {
vec<pii> A;
pii DEFAULT={-1e9,-1e9};
StMx() {
A.resize(LIM<<1, DEFAULT);
fill(all(A), DEFAULT);
}
pii merge(pii a, pii b) {
return max(a,b);
}
void upd(int idx, int val) {
A[idx+LIM]={val,idx};
idx+=LIM;
idx>>=1;
while (idx) {
A[idx]=merge(A[idx*2], A[idx*2+1]);
idx>>=1;
}
}
pii query(int nd, int l, int r, int ql, int qr) {
if (ql<=l && r<=qr) return A[nd];
else if (ql>r || qr<l) return DEFAULT;
else {
int md=(l+r)/2;
return merge(query(nd*2, l, md, ql, qr), query(nd*2+1, md+1, r, ql, qr));
}
}
};
void solve() {
int n,m,k;cin>>n>>m>>k;
vec<int> a(n),b(m),L(k);
for (auto&x:a)cin>>x;
for (auto&x:b)cin>>x;
for (auto&x:L)cin>>x;
// cout<<"DBG "<<n<<m<<k<<endl;
vec<pii> rmlst;
{ // check possible
int idx=0;
for (auto x:b) {
while (idx<n && x!=a[idx]) {
rmlst.pb({a[idx], idx});
idx++;
}
if (idx>=n || a[idx]!=x) {
cout<<"NO\n";
return;
}
idx++;
}
while (idx<n) {
rmlst.pb({a[idx], idx});
idx++;
}
if (rmlst.size()>k) {
cout<<"NO\n";
return;
}
}
sort(all(rmlst));
reverse(all(rmlst));
multiset<int> ls(all(L));
St erased;
StMx mxs;
for (int i=0;i<n;i++) mxs.upd(i, a[i]);
// cout<<"hello"<<endl;
for (auto torm:rmlst) {
int lmst=torm.sc,rmst=torm.sc;
// cout<<"torm "<<torm.fs<<" "<<torm.sc<<endl;
{
int l=0,r=torm.sc;
while (l<=r) {
int md=(l+r)/2;
// cout<<"testing"<<md<<'\n';
auto res=mxs.query(1, 0, LIM-1, md, torm.sc);
// cout<<res.fs<<' '<<res.sc<<" whem"<<md<<endl;
if (res==torm) {
lmst=min(lmst, md);
r=md-1;
} else {
l=md+1;
}
}
}
// cout<<"mid"<<lmst<<endl;
{
int l=torm.sc,r=n-1;
while (l<=r) {
int md=(l+r)/2;
// cout<<"testing2 "<<md<<'\n';
auto res=mxs.query(1, 0, LIM-1, torm.sc, md);
// cout<<res.fs<<' '<<res.sc<<" whem2 "<<md<<endl;
if (res==torm) {
rmst=max(rmst, md);
l=md+1;
} else {
r=md-1;
}
}
}
// cout<<"msts "<<lmst<<' '<<rmst<<endl;
int ecnt=erased.query(1,0,LIM-1, lmst,rmst);
int mxusable=rmst-lmst+1-ecnt;
auto ptr = ls.upper_bound(mxusable);
if (ptr==ls.begin()) {
cout<<"NO\n";
return;
}
ls.erase(--ptr);
mxs.upd(torm.sc, 0);
erased.upd(torm.sc, 1);
}
cout<<"YES\n";
}
signed main() {
ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int tc=1;
cin>>tc;
while (tc--) {
// cout<<"TC" <<tc<<'\n';
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 10020kb
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: 0
Accepted
time: 48ms
memory: 9980kb
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 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 YE...
result:
ok 100 lines
Test #3:
score: 0
Accepted
time: 50ms
memory: 10012kb
input:
99 6 1 6 1 5 3 4 2 6 1 1 2 1 1 1 6 1 1 1 1 1 1 4 1 3 3 4 1 2 1 1 1 2 2 2 1 2 1 2 1 2 1 1 1 1 1 1 2 1 2 1 2 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 3 2 2 3 2 1 2 1 1 2 3 3 1 2 3 1 2 3 1 1 6 1 5 3 4 2 5 6 1 3 4 2 1 1 1 6 4 4 1 6 5 2 3 4 1 2 3 4 5 4 4 6 2 1 1 1 2 1 1 6 5 1 2 1 4 5 6 3 2 1 4 6 3 2 6 3 6 5 6 2 1 3...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO NO YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES NO NO YES YES YES NO YES YES YES NO YES YES NO YES NO YES NO YES YES YES YES YES YES NO YES NO NO YES YES YES YE...
result:
ok 99 lines
Test #4:
score: 0
Accepted
time: 50ms
memory: 10108kb
input:
98 6 1 6 6 1 4 5 2 3 3 1 2 2 1 1 6 4 3 2 2 3 4 1 2 1 3 3 4 1 1 1 1 1 1 6 1 6 6 4 3 1 2 5 1 3 1 3 1 1 5 1 1 1 1 1 1 6 4 4 3 4 1 2 5 6 3 4 1 2 2 4 3 1 6 5 1 4 5 3 6 1 2 4 5 3 1 2 6 1 1 1 1 1 1 5 1 4 1 3 2 4 5 1 5 3 4 4 6 3 4 1 4 2 3 6 5 1 2 5 5 4 6 5 4 1 3 2 1 4 3 2 1 1 1 1 1 1 1 1 1 6 3 5 5 1 3 6 4 2...
output:
YES NO YES YES YES YES YES YES NO NO YES YES NO YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES NO YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES NO YES YES YES YES YES NO YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES NO Y...
result:
ok 98 lines
Test #5:
score: -100
Time Limit Exceeded
input:
60000 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 2 3 1 2 1 2 3 3 1 1 2 3 1 2 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 2 3 2 1 3 2 1 1 1 2 2 1 2 1 2 1 1 1 1 1 1 1 1 2 2 1 1 2 1 2 1 1 1 1 1 1 1 3 1 3 2 3 1 1 2 3 2 3 3 2 2 3 1 2 3 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 3 3 2 1 2 1 1 2 1 3 2 2 1 3 2 3 2 3 ...
output:
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 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 NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES...