Submission #830855

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

mat

/// dwuy: _,\,,,_\,__,\,,_
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK "test"

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX2 = 22;

long long MEMORY = 0;

/// IT'S TIME DOING TRIE HAHAHAHAHAAAAAAAAAAAAAAAAAAAA
struct Node{
    int cnt;
    Node *l, *r;

    Node(){
        this->cnt = 0;
        this->l = this->r = NULL;
    }

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

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

    persistent_Trie(int n = 0){
        this->n = n;
        this->root.resize(n+5);
        for(int i=1; i<(int)this->root.size(); i++) this->root[i] = NULL;
        this->root[0] = new Node();
    }

    void add(int id, int x){
        assert(id<(int)this->root.size());
        root[id] = new Node(root[id-1]);
        Node *cur = root[id];
        for(int mask = MASK(MX2); mask; mask>>=1){
            if(mask&x){
                if(cur->r == NULL) cur->r = new Node();
                else cur->r = new Node(cur->r);
                cur = cur->r;
                MEMORY += sizeof(cur);
            }
            else{
                if(cur->l == NULL) cur->l = new Node();
                else cur->l = new Node(cur->l);
                cur = cur->l;
                MEMORY += sizeof(cur);
            }
            cur->cnt++;
        }
    }

    int cntLower(int x, int id){
        assert(id<(int)this->root.size());
        int d = 0;
        int res = 0;
        int val =   0;
        Node *cur = root[id];
        for(int mask=MASK(MX2); mask; mask>>=1, d++){
            if(val+mask<=x && cur->r!=NULL){
                if(cur->l) res += cur->l->cnt;
                cur = cur->r;
                val += mask;
            }
            else if(cur->l!=NULL) cur = cur->l;
            else break;
        }
        if(val<x && d-1==MX2) res++;
        return res;
    }

    int order(int l, int r, int x){
        return cntLower(x, r) - cntLower(x, l-1);
    }
};

const int MX = 1000005; /// 1e6
int n, m;
int a[MX];
int b[MX];
int c[MX];
bool vist[MX];

void nhap(){
    MEMORY += sizeof(a) + sizeof(b) + sizeof(c);
    cin >> n >> m;
    vector<int> tmp(m);
    for(int i=1; i<=n; i++) cin >> c[i], a[c[i]] = i;
    for(int i=1; i<=m; i++) cin >> b[i], tmp[i-1] = b[i];
    sort(tmp.begin(), tmp.end());
    for(int i=1; i<=m; i++) b[i] = lower_bound(tmp.begin(), tmp.end(), b[i]) - tmp.begin() + 1;
    tmp.clear();
}

int pf[MX];

void solve(){
    persistent_Trie A(n);
    for(int i=1; i<=n; i++) A.add(i, a[i]);
    for(int i=1; i<=n; i++) c[i] = A.order(1, i, a[i]);
    pf[1] = 1;
    bool f = 1;
    for(int i=1, j=2; j<=n; ){
        if(A.order(j-i+1, j, a[j]) == A.order(1, i, a[i])){
            pf[j] = max(pf[j], i);
            i++; j++;
            f = !vist[j];
            vist[j] = 1;
        }
        else if(i!=pf[i-1]) i = pf[i-1], j -= f, f = 0;
        else j++;
    }

    vector<int> ans;
    persistent_Trie B(m);
    for(int i=1; i<=m; i++) B.add(i, b[i]);
    for(int i=1, j=1; i<=m; ){
        if(B.order(i-j+1, i, b[i]) == c[j]){
            if(j==n) ans.push_back(i-n+1), j = pf[j];
            else j++, i++;
        }
        else if(j!=pf[j-1] + 1) j = pf[j-1] + 1;
        else i++;
    }
    cout << ans.size() << endl;
    for(int &x: ans) cout << x << ' ';

//    cerr << setprecision(3) << fixed << 1.0*MEMORY/1000000.0 << "mb";
}

int32_t main(){
    fastIO;
//    file(TASK);

    nhap();
    solve();

    return 0;
}

/**

6 12
2 5 3 4 1 6
10 45 25 30 5 47 31 35 4 50 33 20

6 15
1 4 2 5 3 6
2 8 4 9 6 10 7 11 12 23 26 24 27 25 28
--------------------------------------
3
1 3 10


3 4
1 3 2
1 3 5 4
--------


4 8
1 3 2 4
1 5 2 6 8 7 9 10
-----------------
2
1 4


5 7
5 4 2 3 1
2 4 9 6 3 5 1
-----------------
1
3


4 10
1 2 3 4
1 3 5 7 6 2 4 8 9 10
--------------------
3
1 6 7


4 10
4 3 2 1
1 3 5 7 6 4 8 2 9 10
--------------------
0



5 1   1
1 1   2
7 1   3
8 1   4
2 2   5
10 3   6
3 1   7
12 1   8
13 1   9
4 2   10
15 3   11

16 4   12
6 5   13
17 6   14
9 7   15
18 8   16
19 9   17
11 10   18
20 11   19
14 1   20

21 1   21
22 1   22

**/

• 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