QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#783564#5466. Permutation CompressionyouthpaulWA 1ms3784kbC++204.2kb2024-11-26 10:38:562024-11-26 10:38:56

Judging History

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

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

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

int tot;
int num;

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);
	}
	
	++num;
	if(num == 82){
		std::cout << n << ' ' << m << ' ' << k << endl;
		fore(i, 1, n + 1) std::cout << a[i] << " \n"[i == n];
		fore(i, 1, m + 1) std::cout << b[i] << " \n"[i == m];
		for(auto x : st) std::cout << x << ' ';
	}
	
	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;
    tot = t;
    while(t--){
    	bool tag = solve();
    	if(tot < 82) std::cout << (tag ? "YES" : "NO") << endl;
    	// std::cout << (solve() ? "YES" : "NO") << endl;
    }
    
    return 0;
}











Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3784kb

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

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:

4 1 4
3 2 4 1
3
1 2 3 4 

result:

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