제출 #892153

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
892153		taichi123	Matching (CEOI11_mat)	C++14	0 / 100	403 ms	63408 KiB

mat

#include <bits/stdc++.h>

using namespace std;

#define int int64_t
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#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 TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define sz(a) (int)a.size()
#define mask(i) ((1LL) << (i))
#define bit(x, i) ((x) >> (i) & (1LL))
#define all(x) (x).begin(),(x).end()
#define debug(...) cerr << "#" << __LINE__ << ":[" << #__VA_ARGS__ \
<< "] = [" ,DBG(__VA_ARGS__)

string to_string(const string& s) { return '"' + s + '"'; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...);
}

template <class T> 
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b) : 0); }
template <class T> 
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b) : 0); }

void file() {
    #define task "aa"
    // if(fopen(task".inp", "r")) {
    //     freopen(task".inp", "r", stdin);
    //     freopen(task".out", "w", stdout);
    // }
}

const int INF = 3e18 + 5062007;
const int MOD = 1e9 + 7;
const int MAX = 1e6 + 5;


struct BIT {
    int n, l, r;
    vector <int> bit;
    vector <int> a;
    BIT() {}
    BIT(int n, int *a) {
        this->n = n;
        this->l = this->r = 0;
        this->a.assign(n + 2, 0);
        this->bit.assign(n + 2, 0);
        FOR(i, 1, n) this->a[i] = a[i];
    }

    void add(int idx, int v) {
        if(idx == 0) return;
        for(; idx <= n; idx += idx & -idx) bit[idx] += v;
    }

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

    int Range_update(int u, int v, int x) {
        while(r < v) ++r, add(a[r], 1);
        while(l > u) --l, add(a[l], 1);
        while(r > v) add(a[r], -1), --r;
        while(l < u) add(a[l], -1), ++l;

        return get(x);
    }
};

int n, m, a[MAX], b[MAX], c[MAX], pi[MAX];
vector<int> v;
void solve(int test_case) {
    cin >> n >> m;
    FOR(i, 1, n) {
        int x; cin >> x;
        a[x] = i;
    }

    FOR(i, 1, m) {
        cin >> b[i];
        v.push_back(b[i]);
    }
    sort(all(v));
    FOR(i, 1, m) b[i] = upper_bound(all(v), b[i]) - v.begin();

    BIT mybit[2];
    mybit[0] = mybit[1] = BIT(n, a);

    FOR(i, 1, n) pi[i] = 1;
    for (int i = 1, j = 2; j <= n;) {
        if(mybit[0].Range_update(j - i + 1, j, a[j]) == mybit[1].Range_update(1, i, a[i])) pi[i] = i, ++i, ++j;
        else if(i != pi[i - 1] + 1) i = pi[i - 1] + 1;
        else ++j;
    }

    FOR(i, 1, n) c[i] = mybit[0].Range_update(1, i, a[i]);
    mybit[1] = BIT(m, b);
    vector <int> ans;
    for (int i = 1, j = 1; i <= m;) {
        if(mybit[1].Range_update(i - j + 1, i, b[i]) == c[j]) {
            if(j == n) j = pi[j], ans.push_back(i - n + 1);
            else ++i, ++j;
        }

        else if(j != pi[j - 1] + 1) j = pi[j - 1] + 1;
        else if(j == 2) j = 1;
        else ++i;
    }

    cout << sz(ans) << '\n';
    for (int &x : ans) cout << x << ' ';
}

auto main() -> signed {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    // file();

    int test = 1; 
    // cin >> test; 
    for (int _ = 1; _ <= test; ++_) solve(_);
    cerr << "Time elapsed: " << TIME << " s.\n";
    return 0;
}
//567
/*
6 12
2 5 3 4 1 6
10 45 25 30 5 47 31 35 4 50 33 20
*/

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