QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#142383 | #5466. Permutation Compression | ElDiablo# | RE | 1ms | 3536kb | C++14 | 4.3kb | 2023-08-19 01:04:16 | 2023-08-19 01:04:18 |
Judging History
answer
#pragma GCC optimize("O3,unroll-loops")
#include <algorithm>
#include <cmath>
#include <cassert>
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <bitset>
#include <vector>
#include <queue>
#include <numeric>
#define f(x, a, b) for (int x = a; x < b; x++)
#define fm(x, a, b) for (int x = a; x > b; x--)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define sz(a) int((a).size())
using namespace std;
typedef unsigned long long ll;
typedef long long int li;
const li mod=1e9+7;
int maxq(int l, int r, vector<int> &tree) {
int n = tree.size();
l += n/2;
r += n/2;
int ans = 0;
while(l<r) {
if (l&1) {
ans = max(ans,tree[l]);
l++;
}
if (r&1) {
r--;
ans = max(ans,tree[r]);
}
l >>= 1;
r >>= 1;
}
return ans;
}
int minq(int l, int r, vector<int> &tree) {
int n = tree.size();
l += n/2;
r += n/2;
int ans = 1e9;
while(l<r) {
if (l&1) {
ans = min(ans,tree[l]);
l++;
}
if (r&1) {
r--;
ans = min(ans,tree[r]);
}
l >>= 1;
r >>= 1;
}
return ans;
}
int sumq(int l, int r, vector<int> &tree) {
int n = tree.size();
l += n/2;
r += n/2;
if (l>=r) return 0;
int ans = 0;
while(l<r) {
if (l&1) {
ans += tree[l];
l++;
}
if (r&1) {
r--;
ans += tree[r];
}
l >>= 1;
r >>= 1;
}
return ans;
}
void update(int i, int val, vector<int> &tree, bool mx) {
int n = tree.size();
i += n/2;
tree[i] = val;
while(i>1) {
i >>= 1;
if (mx)
tree[i] = max(tree[2*i],tree[2*i+1]);
else
tree[i] = min(tree[2*i],tree[2*i+1]);
}
}
void update2(int i, int val, vector<int> &tree) {
int n = tree.size();
i += n/2;
tree[i] = val;
while(i>1) {
i >>= 1;
tree[i] = tree[2*i] + tree[2*i+1];
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >>t;
while(t--) {
int n,m,k;
cin >> n >> m >> k;
vector<int> a(n);
f(i,0,n) cin >> a[i];
vector<int> b(m);
f(i,0,m) cin >> b[i];
vector<pair<int,int> > rem;
int i1=0,i2=0;
while(i1<n) {
if(i2 < m && a[i1]==b[i2]) {
i1++;
i2++;
}
else {
rem.pb(mp(a[i1],0));
i1++;
}
}
if (i2 < m) {
cout << "NO\n";
continue;
}
vector<int> l(k);
f(i,0,k) cin >> l[i];
sort(all(l));
int l1 = 1;
while(l1<=n)
l1 <<= 1;
vector<int> tree(2*l1,-1);
i1=0;
vector<int> tl(n);
f(i,0,n) {
if (i1 < sz(rem) && rem[i1].first == a[i]) {
tl[i] = maxq(rem[i1].first,n,tree);
rem[i1].second = i;
i1++;
}
else {
update(a[i],i,tree,true);
}
}
tree = vector<int>(2*l1,n);
vector<int> tr(n);
i1 = sz(rem)-1;
fm(i,n-1,-1) {
if (i1 >= 0 && rem[i1].first == a[i]) {
tr[i] = minq(rem[i1].first,n,tree);
i1--;
}
else {
update(a[i],i,tree,false);
}
}
sort(all(rem));
tree = vector<int>(2*l1,0);
vector<int> tsum(sz(rem));
fm(i,sz(rem)-1,-1) {
tsum[i] = tr[rem[i].second]-tl[rem[i].second]-1 - sumq(tl[rem[i].second]+1,tr[rem[i].second]-1,tree);
update2(rem[i].second,1,tree);
}
i1 = sz(rem)-1;
fm(i,k-1,-1) {
// cout << i1 << " " << tsum[i1] << " " << l[i] << "\n";
if (i1>=0 && tsum[i1] >= l[i]) {
i1--;
}
}
if (i1 < 0) {
cout << "YES\n";
}
else {
cout << "NO\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3536kb
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
Runtime Error
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 ...