Submission #830383

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
830383	2023-08-19T05:06:32 Z	winthemcut3	Matching (CEOI11_mat)	C++14	100 / 100	509 ms	55876 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] && i > l[j] && a[i - l[j]] > a[i]) return false;
        if(r[j] && i > r[j] && a[i - r[j]] < a[i]) return false;
        //cerr << '*';
        return true;
    } else {
        if(j == n+1) return false;
        if(l[j] && i > l[j] && b[i - l[j]] > b[i]) return false;
        if(r[j] && i > 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	464 KB	Output is correct
2	Correct	0 ms	340 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	340 KB	Output is correct
2	Correct	1 ms	356 KB	Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	872 KB	Output is correct
2	Correct	4 ms	868 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	4564 KB	Output is correct
2	Correct	32 ms	3376 KB	Output is correct
3	Correct	63 ms	5804 KB	Output is correct
4	Correct	59 ms	5844 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	5348 KB	Output is correct
2	Correct	54 ms	4048 KB	Output is correct
3	Correct	39 ms	4640 KB	Output is correct
4	Correct	38 ms	5340 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	5428 KB	Output is correct
2	Correct	35 ms	5000 KB	Output is correct
3	Correct	50 ms	4684 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	252 ms	26796 KB	Output is correct
2	Correct	509 ms	55876 KB	Output is correct
3	Correct	192 ms	15096 KB	Output is correct

Subtask #9
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	236 ms	27700 KB	Output is correct
2	Correct	296 ms	15072 KB	Output is correct
3	Correct	482 ms	51296 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	217 ms	18520 KB	Output is correct
2	Correct	189 ms	25860 KB	Output is correct
3	Correct	266 ms	20620 KB	Output is correct
4	Correct	262 ms	53992 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	201 ms	20584 KB	Output is correct
2	Correct	258 ms	20684 KB	Output is correct
3	Correct	91 ms	11924 KB	Output is correct
4	Correct	308 ms	51412 KB	Output is correct

Submission #830383

Compilation message