QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#130750#5466. Permutation CompressiontselmegkhCompile Error//C++204.0kb2023-07-24 22:53:152023-07-24 22:53:16

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:53:16]
  • 评测
  • [2023-07-24 22:53:15]
  • 提交

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]);
        }
    }
    assert(sz(v) == m);
    
    multiset<int> tools;
    for(int i = 0; i < k; i++){
        int x; cin >> x;
        tools.insert(x);
    }
    
    for(int i = 1; i <= m; i++){
        if(y[i] != v[i - 1]){
            cout << "NO\n";
            return;
        }
    }
    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

answer.code: In function ‘void solve()’:
answer.code:110:5: error: ‘assert’ was not declared in this scope
  110 |     assert(sz(v) == m);
      |     ^~~~~~
answer.code:12:1: note: ‘assert’ is defined in header ‘<cassert>’; did you forget to ‘#include <cassert>’?
   11 | #include <iomanip>
  +++ |+#include <cassert>
   12 | using namespace std;