Submission #1096536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096536		dwuy	Matching (CEOI11_mat)	C++14	100 / 100	597 ms	44296 KiB

mat

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

struct BIT{
    int n;
    vector<int> tree;
    
    BIT(int n = 0){
        this->n = n;
        this->tree.assign(n + 5, 0);
    }

    void update(int idx, int val){
        for(; idx<=n; idx+=-idx&idx) tree[idx] += val;
    }

    int get(int idx){
        int res = 0;
        for(; idx; idx-=-idx&idx) res += tree[idx];
        return res;
    }
};

typedef pair<int, int> pii;
const int MX = 1000005;
int n, m;
int l = 1, r = 0, u = 1, v = 0;
int a[MX], b[MX], p[MX];
int pa[MX];
BIT A, B;

int Ga(int fx, int fy){
    while(r < fy) r++, A.update(a[r], 1);
    while(l < fx) A.update(a[l], -1), l++;
    return A.get(a[fy]);
}

int Gb(int fx, int fy){
    while(v < fy) v++, B.update(b[v], 1);
    while(u < fx) B.update(b[u], -1), u++;
    return B.get(b[fy]);
}

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;
    }
    vector<int> rv(m);
    for(int i=1; i<=m; i++){
        cin >> b[i];
        rv[i-1] = b[i];
    }
    sort(rv.begin(), rv.end());
    for(int i=1; i<=m; i++) b[i] = lower_bound(rv.begin(), rv.end(), b[i]) - rv.begin() + 1;
    
    A = BIT(n);
    for(int i=1; i<=n; i++) pa[i] = Ga(1, i);

    l = u = 1, r = v = 0;
    A = BIT(n);
    B = BIT(m);
    int l = 1, r = 0, u = 1, v = 0;
    for(int i=2, j=0; i<=n; i++){
        while(j != 0 && pa[j + 1] != Ga(i - j, i)) j = p[j];
        if(pa[j + 1] == Ga(i - j, i)) p[i] = ++j;
    }
    vector<int> ans;
    for(int i=1, j=0; i<=m; i++){
        while(j != 0 && pa[j + 1] != Gb(i - j, i)) j = p[j];
        if(pa[j + 1] == Gb(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;
}

Compilation message (stderr)

mat.cpp: In function 'int32_t main()':
mat.cpp:69:9: warning: unused variable 'l' [-Wunused-variable]
   69 |     int l = 1, r = 0, u = 1, v = 0;
      |         ^
mat.cpp:69:16: warning: unused variable 'r' [-Wunused-variable]
   69 |     int l = 1, r = 0, u = 1, v = 0;
      |                ^
mat.cpp:69:23: warning: unused variable 'u' [-Wunused-variable]
   69 |     int l = 1, r = 0, u = 1, v = 0;
      |                       ^
mat.cpp:69:30: warning: unused variable 'v' [-Wunused-variable]
   69 |     int l = 1, r = 0, u = 1, v = 0;
      |                              ^

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