Submission #830385

#	Time	Username	Problem	Language	Result	Execution time	Memory
830385		winthemcut3	Matching (CEOI11_mat)	C++14	100 / 100	533 ms	39804 KiB

mat

#include <bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define PB push_back
#define ALL(v) (v).begin(), (v).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define fi   first
#define se   second
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;

/** END OF TEMPLATE **/

const int mxN = 1e6 + 7;
struct DSU {
    vector<int> e, p;
    DSU(int t) : e(t+1, -1) {
        p.resize(t+1);
        FOR(i, 0, t) p[i] = i;
    }
    int rep(int u) { return e[u] < 0 ? u : e[u] = rep(e[u]); }
    int get(int u) { return p[rep(u)]; }
    void unite(int u, int v, bool st) {
        u = rep(u); v = rep(v);
        if(u == v) return;
        if(e[u] > e[v]) swap(u, v);
        e[u] += e[v]; e[v] = u;
        if(st) p[u] = max(p[u], p[v]);
        else p[u] = min(p[u], p[v]);
    }
};
int l[mxN], r[mxN], pos[mxN];
int n, m;
int a[mxN], b[mxN], pi[mxN];
bool check(int st, int i, int j) {
    if(!st) {
        //cerr << i << ' ' << j << ' ' << a[i] << ' ' << a[i-r[j]] << '\n';
        if(l[j] && a[i - l[j]] > a[i]) return false;
        if(r[j] && a[i - r[j]] < a[i]) return false;
        //cerr << '*';
        return true;
    } else {
        if(j == n+1) return false;
        if(l[j] && b[i - l[j]] > b[i]) return false;
        if(r[j] && b[i - r[j]] < b[i]) return false;
        return true;
    }
}
void calc() {
    DSU L(n+2), R(n+2);
    pos[0] = 0, pos[n+1] = n+1;
    FORD(i, n, 1) {
        int u = a[i];
        int t1 = pos[L.get(u-1)], t2 = pos[R.get(u+1)];
        if(t1) l[i] = i - t1;
        if(t2 < n+1) r[i] = i - t2;
        L.unite(u, u-1, 0);
        R.unite(u, u+1, 1);
    }
//    cerr << "\nL: ";
//    FOR(i, 1, n) cout << l[i] << ' ';
//    cerr << "\nR: ";
//    FOR(i, 1, n) cout << r[i] << ' ';
//    cerr << '\n';
}
int main()
{
    FastIO;
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    cin >> n >> m;
    FOR(i, 1, n) {
        cin >> pos[i];
        a[pos[i]] = i;
    }
    vector<int> t;
    FOR(i, 1, m) cin >> b[i], t.PB(b[i]);
    sort(ALL(t));
    FOR(i, 1, m)
        b[i] = lower_bound(ALL(t), b[i]) - t.begin() + 1;
    calc();
    FOR(i, 2, n) {
        int j = pi[i-1];
        while(j > 0 && !check(0, i, j+1))
            j = pi[j];
        if(check(0, i, j+1)) j++;
        pi[i] = j;
    }
    int j = 0;
    vector<int> res;
    FOR(i, 1, m) {
        while(j > 0 && !check(1, i, j+1))
            j = pi[j];
        if(check(1, i, j+1)) j++;
        if(j == n) res.PB(i - n + 1);
    }
    cout << res.size() << '\n';
    for(auto &x : res) cout << x << ' ';
    return 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