QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#783556#5466. Permutation CompressionyouthpaulWA 1ms3628kbC++203.8kb2024-11-26 10:35:382024-11-26 10:35:39

Judging History

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

  • [2024-11-26 10:35:39]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3628kb
  • [2024-11-26 10:35:38]
  • 提交

answer

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;

const int INF=0x3f3f3f3f;
const long long INFLL=1e18;

typedef long long ll;

template<class Info>
struct SegmentTree {
    int n;
    std::vector<Info> info;
    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    SegmentTree(int n_, std::vector<T> init_) {
        init(n_, init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(n_, std::vector(n_ + 1, v_));
    }
    template<class T>
    void init(int n_, std::vector<T> init_) {
        n = n_;
        info.assign(4 << std::__lg(n), Info());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void update(int p, int l, int r, int qp, const Info& v){
        if(l == r){
            info[p] = info[p] + v;
            return;
        }
        int m = l + r >> 1;
        if(qp <= m) update(p << 1, l, m, qp, v);
        else update(p << 1 | 1, m + 1, r, qp, v);
        pull(p);
    }
    void update(int qp, const Info& v){
        update(1, 1, n, qp, v);
    }
    Info query(int p, int l, int r, int ql, int qr){
        if(ql <= l && r <= qr) return info[p];
        if(qr < l || r < ql) return Info();
        int mid = l + r >> 1;
        return query(p << 1, l, mid, ql, qr) + query(p << 1 | 1, mid + 1, r, ql, qr);
    }
    Info query(int ql, int qr){
        return query(1, 1, n, ql, qr);
    }
};

struct Info {
    int mx = 0;
    int cnt = 0;
};

Info operator+(Info a, Info b) {
    return {std::max(a.mx, b.mx), a.cnt + b.cnt};
}

bool solve(){
	int n, m, k;
	std::cin >> n >> m >> k;
	std::vector<int> a(n + 1), b(m + 1), p(n + 1);
	std::multiset<int> st;
	fore(i, 1, n + 1){
		std::cin >> a[i];
		p[a[i]] = i;
	}
	fore(i, 1, m + 1) std::cin >> b[i];
	fore(i, 0, k){
		int l;
		std::cin >> l;
		st.insert(l);
	}
	if(n - k > m) return false;
	int idx = 1;
	std::vector<bool> del(n + 1, true);
	fore(i, 1, m + 1){
		del[b[i]] = false;
		while(idx <= n){
			if(a[idx] == b[i]) break;
			++idx;
		}
		if(idx > n) return false;
	}
	
	std::vector<int> vec;
	std::vector<Info> info(n + 1);
	fore(i, 1, n + 1) info[i] = {a[i], 1};
	SegmentTree<Info> seg(n, info);
	fore(i, 1, n + 1)
		if(del[i]){
			vec.push_back(i);
		}
	
	while(!vec.empty()){
		int x = vec.back();
		vec.pop_back();
		int pos = p[x];
		int l = 1, r = pos - 1;
		int lp = 0;
		while(l <= r){
			int mid = l + r >> 1;
			Info info = seg.query(mid, pos);
			if(info.mx > x){
				lp = mid;
				l = mid + 1;
			}
			else r = mid - 1;
		}
		
		int rp = n + 1;
		l = pos + 1, r = n;
		while(l <= r){
			int mid = l + r >> 1;
			Info info = seg.query(pos, mid);
			if(info.mx > x){
				rp = mid;
				r = mid - 1;
			}
			else l = mid + 1;
		}
		
		++lp;
		--rp;
		int len = seg.query(lp, rp).cnt;
		auto it = st.upper_bound(len);
		if(it == st.begin()) return false;
		--it;
		st.erase(it);
		
		
		seg.update(p[x], {0, 0});
	}
	
	return true;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t;
    std::cin >> t;
    while(t--){
    	std::cout << (solve() ? "YES" : "NO") << endl;
    }
    
    return 0;
}











详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3628kb

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

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:

wrong answer 82nd lines differ - expected: 'YES', found: 'NO'