QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#713835#5466. Permutation Compressionqtoq#WA 1ms3824kbC++173.8kb2024-11-05 20:39:562024-11-05 20:39:57

Judging History

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

  • [2024-11-05 20:39:57]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3824kb
  • [2024-11-05 20:39:56]
  • 提交

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;
  }
};

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];
  }
  for(int i = 0; i + 1 < m; ++i) {
    if(inv[b[i]] > inv[b[i+1]]) {
      cout << "NO\n";
      return ;
    }
  }
  multiset<int> le;
  for(int i = 0; i < k; ++i) {
    int l; cin >> l;
    le.insert(l);
  }
  vt<int> kill(n, true);
  for(auto x: b) {
    kill[x] = false;
  }
  vt<int> pos(n);
  {
    int id = 0;
    for(int i = 0; i < n; ++i) {
      if(kill[a[i]]) {
        continue;
      }
      pos[i] = id++;
    }
  }
  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], pos[i]);
    }
  }
  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], pos[i]);
    }
  }
  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];
  });
  bool res = true;
  for(auto i: ids) {
    int mx = r[i] - l[i];
    auto it = le.lower_bound(mx + 1);
    if(it == le.begin()) {
      res = false;
      break;
    }
    --it;
    le.erase(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: 3620kb

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: 3824kb

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
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
NO
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
YES
YES
YES
...

result:

wrong answer 23rd lines differ - expected: 'NO', found: 'YES'