QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#130749#5466. Permutation CompressiontselmegkhRE 2ms9720kbC++204.0kb2023-07-24 22:51:532023-07-24 22:51:54

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-24 22:51:54]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:9720kb
  • [2023-07-24 22:51:53]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iomanip>
using namespace std;

const int N = 2e5 + 5, inf = 1e9;
#define pb push_back
#define mp make_pair
#define ll long long
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define sz(x) (int)x.size()
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;

struct Node {
    int val;
    int sum;
    Node(){
        val = sum = 0;
    }
};

Node t[N * 4];
int a[N], y[N];

Node combine(Node a, Node b){
    Node c;
    c.sum = a.sum + b.sum;
    c.val = max(a.val, b.val);
    return c;
}

void build(int v, int l, int r){
    if(l == r){
        t[v].val = a[l];
        t[v].sum = 0;
        return;
    }
    int mid = (l + r) / 2;
    build(v * 2, l, mid);
    build(v * 2 + 1, mid + 1, r);
    t[v] = combine(t[v * 2], t[v * 2 + 1]);
}

void update(int v, int l, int r, int pos){
    if(l == pos && r == pos){
        t[v].val = -inf;
        t[v].sum = 1;
        return;
    }
    if(l > pos || r < pos)return;
    int mid = (l + r) / 2;
    update(v * 2, l, mid, pos);
    update(v * 2 + 1, mid + 1, r, pos);
    t[v] = combine(t[v * 2], t[v * 2 + 1]);
}
int query(int v, int l, int r, int ql, int qr, bool isSum){
    if(l > qr || r < ql){
        if(isSum)return 0;
        return -inf;
    }
    if(ql <= l && r <= qr){
        if(isSum)return t[v].sum;
        return t[v].val;
    }
    int mid = (l + r) / 2;
    if(isSum){
        return query(v * 2, l, mid, ql, qr, isSum) + query(v * 2 + 1, mid + 1, r, ql, qr, isSum);
    } else {
        return max(query(v * 2, l, mid, ql, qr, isSum), query(v * 2 + 1, mid + 1, r, ql, qr, isSum));
    }
}
void solve(){
    int n, m, k;
    cin >> n >> m >> k;
    vi pos(n + 1);
    vector<bool> vis(n + 1);
    set<ii> s;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        pos[a[i]] = i;
    }
    build(1, 1, n);
    for(int i = 1; i <= n; i++){
        s.insert({i, pos[i]});
    }
    bool flag = false;
    for(int i = 1; i <= m; i++){
        cin >> y[i];
        vis[y[i]] = true;
        s.erase(s.lower_bound({y[i], -1}));
    }
    vi v;
    for(int i = 1; i <= n; i++){
        if(vis[a[i]]){
            v.pb(a[i]);
        }
    }
    for(int i = 1; i <= m; i++){
        if(y[i] != v[i - 1]){
            cout << "NO\n";
            return;
        }
    }
    
    multiset<int> tools;
    for(int i = 0; i < k; i++){
        int x; cin >> x;
        tools.insert(x);
    }
    while(!s.empty()){
        auto x = s.rbegin();
        int todelete = x->ff, idx = x->ss;
        s.erase(*x);
        int l = idx, r = n;
        int fl, fr;
        
        while(l != r){
            int mid = (l + r + 1) / 2;
            if(query(1, 1, n, idx, mid, false) == todelete){
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        
        fr = l;
        l = 1, r = idx;
        while(l != r){
            int mid = (l + r) / 2;
            if(query(1, 1, n, mid, idx, false) == todelete){
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        fl = l;

        int value = fr - fl + 1 - query(1, 1, n, fl, fr, true);
        if(tools.empty()){
            cout << "NO\n";
            return;
        }
        auto it = tools.upper_bound(value);
        if(it != tools.begin()){
            it--;
        }
        int tool = (*it);
        if(tool > value){
            cout << "NO\n";
            return;
        }
        tools.erase(it);
        update(1, 1, n, idx);
    }
    cout << "YES\n";
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 9720kb

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
Dangerous Syscalls

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:


result: