Submission #1240669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240669		nguyendinhtien	Matching (CEOI11_mat)	C++17	100 / 100	146 ms	35592 KiB

mat

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define N 1000000
#define ll long long
#define MOD 1000000007
#define inf 2000000000
#define llf 1000000000000000000
// #define base 31
#define MASK(i) (1 << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define fi first
#define se second
#define el '\n'
#define oset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;
using namespace __gnu_pbds;

int n, m;
int idx[N + 5], s[2 * N + 5], lt[N + 5], rt[N + 5], pi[2 * N + 5];

struct linked
{
    int n, *l, *r;

    linked(int _n) : n(_n), l(new int[_n + 5]), r(new int[_n + 5])
    {
        for(int i = 1; i <= n; i++)
        {
            l[i] = i - 1;
            r[i] = i + 1;
        }
    }

    void del(int i)
    {
        int _l = l[i], _r = r[i];
        r[_l] = _r;
        l[_r] = _l;
    }
};

bool check(int i, int j)
{
    if(i == n + 1) return false;
    if(lt[i] && s[j - i + lt[i]] > s[j]) return false;
    if(rt[i] && s[j + rt[i] - i] < s[j]) return false;
    return true;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen(".INP", "r", stdin);
    // freopen(".OUT", "w", stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> idx[i];
        s[idx[i]] = i;
    }

    s[n + 1] = 0;
    for(int i = n + 2; i <= n + m + 1; i++) cin >> s[i];
    linked lk(n);

    for(int i = n; i >= 1; i--)
    {
        lt[i] = idx[lk.l[s[i]]];
        rt[i] = idx[lk.r[s[i]]];
        lk.del(s[i]);
    }

    vector<int> ans(0);
    for(int i = 2; i <= n + m + 1; i++)
    {
        if(i == n + 1) continue;
        int tmp = pi[i - 1];
        while(tmp > 0 && !check(tmp + 1, i)) tmp = pi[tmp];
        if(check(tmp + 1, i)) pi[i] = tmp + 1;
        if(i > n + 1 && pi[i] == n) ans.push_back(i - 2 * n);
    }

    cout << ans.size() << el;
    for(int x : ans) 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