QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#714648#5466. Permutation CompressionqtoqWA 1ms3816kbC++174.4kb2024-11-06 01:35:122024-11-06 01:35:14

Judging History

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

  • [2024-11-06 01:35:14]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3816kb
  • [2024-11-06 01:35:12]
  • 提交

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], -1);
  }
  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);
  }
  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 = 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: 100
Accepted
time: 0ms
memory: 3816kb

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: 1ms
memory: 3664kb

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'