Submission #830385

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
830385	2023-08-19T05:12:37 Z	winthemcut3	Matching (CEOI11_mat)	C++14	100 / 100	533 ms	39804 KB

#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.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	324 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	852 KB	Output is correct
2	Correct	4 ms	804 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	836 KB	Output is correct
2	Correct	4 ms	852 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	3408 KB	Output is correct
2	Correct	30 ms	2280 KB	Output is correct
3	Correct	60 ms	3864 KB	Output is correct
4	Correct	72 ms	3936 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	3956 KB	Output is correct
2	Correct	53 ms	2344 KB	Output is correct
3	Correct	40 ms	2924 KB	Output is correct
4	Correct	37 ms	4328 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	4060 KB	Output is correct
2	Correct	39 ms	3732 KB	Output is correct
3	Correct	49 ms	3168 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	256 ms	16920 KB	Output is correct
2	Correct	533 ms	39804 KB	Output is correct
3	Correct	187 ms	7672 KB	Output is correct

Subtask #9
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	237 ms	17772 KB	Output is correct
2	Correct	310 ms	8560 KB	Output is correct
3	Correct	517 ms	38272 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	219 ms	10744 KB	Output is correct
2	Correct	182 ms	19364 KB	Output is correct
3	Correct	254 ms	11024 KB	Output is correct
4	Correct	259 ms	39772 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	200 ms	12600 KB	Output is correct
2	Correct	255 ms	10948 KB	Output is correct
3	Correct	89 ms	8000 KB	Output is correct
4	Correct	323 ms	36720 KB	Output is correct

Submission #830385

Compilation message