QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#714645#5466. Permutation CompressionqtoqWA 0ms3616kbC++174.5kb2024-11-06 01:33:532024-11-06 01:33:53

Judging History

你现在查看的是最新测评结果

  • [2024-11-06 01:33:53]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3616kb
  • [2024-11-06 01:33:53]
  • 提交

answer

#include <bits/stdc++.h>


using namespace std;

template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
 void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef ONPC
  #define deb(...) cerr << '[' << __FILE__ << ':' << __LINE__ << "] (" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
  #pragma GCC optimize("O3,unroll-loops")
  #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  #define deb(...)
#endif

// c++ short types
#define vt vector
//typedef long long ll;
typedef long double ld;

void whattime() { cout << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl; }
// const int mod = 1e9 + 7;
const int mod = 998244353;
const int inf = 1e9;
const int64_t infll = 1e13;
bool debug = false;
const ld eps = 1e-9;
const ld pi = acos(-1);
mt19937_64 rng((int) chrono::steady_clock::now().time_since_epoch().count());

struct Segmax {
  vt<int> t;
  int n;
  Segmax(int _n) : n(_n) {
    t = vt<int>(2*n, - inf);
  }
  void update(int pos, int value) {
    pos += n;
    while(pos) {
      t[pos] = max(t[pos], value);
      pos >>= 1;
    }
  }
  int get(int l, int r) {
    int res = -2*n;
    for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if(l&1){ 
        res = max(res, t[l++]);
      }
      if(r&1){
        res = max(res, t[--r]);
      }
    }
    return res;
  }
};

struct Segmin {
  vt<int> t;
  int n;
  Segmin(int _n) : n(_n) {
    t = vt<int>(2*n, + inf);
  }
  void update(int pos, int value) {
    pos += n;
    while(pos) {
      t[pos] = min(t[pos], value);
      pos >>= 1;
    }
  }
  int get(int l, int r) {
    int res = 2*n;
    for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if(l&1){ 
        res = min(res, t[l++]);
      }
      if(r&1){
        res = min(res, t[--r]);
      }
    }
    return res;
  }
};
struct Segsum {
  int n;
  vt<int> t;
  Segsum(int _n) : n(_n) {
    t = vt<int>(2*n, 0);
  }
  void update(int pos, int dx) {
    pos += n;
    while(pos) {
      t[pos] += dx;
      pos >>= 1;
    }
  }
  int get(int l, int r) {
    int ret = 0;
    for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if(l&1){ 
        ret += t[l++];
      }
      if(r&1){
        ret += t[--r];
      }
    }
    return ret;
  }
};

void solve() {
  int n, m, k;
  cin >> n >> m >> k;
  vt<int> a(n), b(m);
  vt<int> inv(n);
  for(int i = 0; i < n; ++i) {
    cin >> a[i];
    --a[i];
    inv[a[i]] = i;
  }
  for(int i = 0; i < m; ++i) {
    cin >> b[i];
    --b[i];
  }
  multiset<int> le;
  for(int i = 0; i < k; ++i) {
    int l; cin >> l;
    le.insert(l);
  }
  for(int i = 0; i + 1 < m; ++i) {
    if(inv[b[i]] >= inv[b[i+1]]) {
      cout << "NO\n";
      return ;
    }
  }
  vt<int> kill(n, true);
  for(auto x: b) {
    kill[x] = false;
  }
  vt<int> l(n, -1), r(n, n);
  Segmax sm(n);
  for(int i = 0; i < n; ++i) {
    l[i] = sm.get(a[i] + 1, n);
    if(not kill[a[i]]) {
      sm.update(a[i], i);
    }
    l[i] = max(l[i], 0);
  }
  Segmin smin(n);
  for(int i = n-1; i >= 0; --i) {
    r[i] = smin.get(a[i] + 1, n);
    if(not kill[a[i]]) {
      smin.update(a[i], i);
    }
    r[i] = min(r[i], n-1);
  }
  vt<int> ids;
  for(int i = 0; i < n; ++i) if(kill[a[i]]) {
    ids.push_back(i);
  }
  sort(ids.begin(), ids.end(), [&](int i, int j) -> bool {
      return a[i] > a[j];
  });
  Segsum st(n);
  for(int i = 0; i < n; ++i) {
    st.update(i, +1);
  }
  bool res = true;
  for(auto i: ids) {
    if(le.empty()) {
      res = false;
      break;
    }
    int mx = 2 * n;
    if(l[i] >= 0 and r[i] < n) {
      mx = st.get(l[i]+1, r[i]); // [l[i]+1; r[i]-1]
    }
    if(*le.rbegin() <= mx) {
      le.erase(le.find(*le.rbegin()));
      continue;
    }
    auto it = le.lower_bound(mx + 1);
    if(it == le.begin()) {
      res = false;
      break;
    }
    st.update(i, -1);
    le.erase(prev(it));
  }
  cout << (res ? "YES" : "NO") << '\n';
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int tt = 1;;
	if(debug) {
		tt = 1e3;
	} else {
		cin >> tt;
	}

	for(int t = 0; t < tt; ++t) {
		solve();
	}
	
#ifdef ONPC
	whattime();
#endif
	
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3616kb

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:

NO
YES
NO

result:

wrong answer 1st lines differ - expected: 'YES', found: 'NO'