Submission #1096505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096505		dwuy	Matching (CEOI11_mat)	C++14	36 / 100	221 ms	65536 KiB

mat

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

struct Node{
    int cnt;
    Node *l, *r;

    Node() : cnt(0), l(NULL), r(NULL) {}

    Node(const Node *other){
        cnt = other->cnt;
        l = other->l;
        r = other->r;
    }
};

struct SMT{
    int n;
    vector<Node*> root;

    SMT(int n = 0){
        this->n = n;
        this->root.assign(n + 5, NULL);
        root[0] = new Node();
    }

    void cheese_burger(int i){
        root[i] = new Node(root[i-1]);
    }

    void update(Node *cur, int l, int r, const int &pos){
        if(l == r){
            cur->cnt++;
            return;
        }
        int mid = (l + r)>>1;
        if(pos <= mid){
            if(cur->l == NULL) cur->l = new Node();
            else cur->l = new Node(cur->l);
            update(cur->l, l, mid, pos);
        }
        else{
            if(cur->r == NULL) cur->r = new Node();
            else cur->r = new Node(cur->r);
            update(cur->r, mid + 1, r, pos);
        }
        cur->cnt = (cur->l? cur->l->cnt : 0) + (cur->r? cur->r->cnt : 0);
    }

    void update(int i, int pos){
        update(root[i], 1, n, pos);
    }

    int get(Node *cur, int l, int r, const int &u, const int &v){
        if(l > v || r < u || cur == NULL) return 0;
        if(l >= u && r <= v) return cur->cnt;
        int mid = (l + r)>>1;
        return get(cur->l, l, mid, u, v) + get(cur->r, mid + 1, r, u, v);
    }

    int get(int i, int l, int r){
        return get(root[i], 1, n, l, r);
    }
};

typedef pair<int, int> pii;
const int MX = 1000005;
int n, m;
int a[MX], b[MX], p[MX];
int idA[MX], idB[MX];
pii _a[MX], _b[MX];

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for(int i=1; i<=n; i++){
        int x; cin >> x;
        a[x] = i;
        _a[x] = {i, x};
    }
    for(int i=1; i<=m; i++){
        cin >> b[i];
        _b[i] = {b[i], i};
    }

    SMT A(n);
    SMT B(m);
    sort(_a + 1, _a + 1 + n);
    sort(_b + 1, _b + 1 + m);
    for(int i=1; i<=n; i++){
        idA[_a[i].se] = i;
        A.cheese_burger(i);
        A.update(i, _a[i].se);
    }
    for(int i=1; i<=m; i++){
        idB[_b[i].se] = i;
        B.cheese_burger(i);
        B.update(i, _b[i].se);
    }

    for(int i=2, j=0; i<=n; i++){
        while(j != 0 && A.get(idA[j + 1], 1, j + 1) != A.get(idA[i], i - j, i)) j = p[j];
        if(A.get(idA[j + 1], 1, j + 1) == A.get(idA[i], i - j, i)) p[i] = ++j;
    }

    vector<int> ans;
    for(int i=1, j=0; i<=m; i++){
        while(j != 0 && A.get(idA[j + 1], 1, j + 1) != B.get(idB[i], i - j, i)) j = p[j];
        if(A.get(idA[j + 1], 1, j + 1) == B.get(idB[i], i - j, i)) j++;
        if(j == n){
            ans.push_back(i - n + 1);
            j = p[j];
        }
    }

    cout << ans.size() << endl;
    for(int x: ans) cout << x << ' ';

    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10