Submission #205849

#	Time	Username	Problem	Language	Result	Execution time	Memory
205849		parsa_mobed	Matching (CEOI11_mat)	C++14	63 / 100	2096 ms	47340 KiB

mat

#include <bits/stdc++.h>

using namespace std;
#define mid ((L+R)>>1)
const int N = 1e6 + 5;
int MOD = 1e9 + 7, Base = 1e6 + 3;
int inp[N], h[N], a[N], b[N], p[N], pw[N], seg[N<<2], lazy[N<<2], fen[N], Hash, n, m;
vector <int> ans, vec;

void apply(int id, int val) {
    seg[id] = (1ll * seg[id] * pw[val]) % MOD, lazy[id] += val;
}
void shift(int id) {
    if (lazy[id] == 0) return ;
    apply(id<<1, lazy[id]), apply(id<<1|1, lazy[id]);
    lazy[id] = 0;
}
void Set(int l, int val, int L = 0, int R = m, int id = 1) {
    if (l + 1 <= L || R <= l) return ;
    if (l <= L && R <= l + 1) {
        seg[id] = val;
        return ;
    }
    shift(id);
    Set(l, val, L, mid, id<<1);
    Set(l, val, mid, R, id<<1|1);
    seg[id] = seg[id<<1] + seg[id<<1|1];
    if (seg[id] >= MOD) seg[id] -= MOD;
}
int Get(int l, int r, int L = 0, int R = m, int id = 1) {
    if (r <= L || R <= l) return 0;
    if (l <= L && R <= r) return seg[id];
    shift(id);
    int x = Get(l, r, L, mid, id<<1) + Get(l, r, mid, R, id<<1|1);
    if (x >= MOD) x -= MOD;
    return x;
}

void add_fen(int idx, int val) {
    for (idx++; idx < N; idx += idx&(-idx)) fen[idx] += val;
}
int get_fen(int idx) {
    int res = 0;
    for (idx++; idx; idx -= idx&(-idx)) res += fen[idx];
    return res;
}

int main()
{
    pw[0] = 1;
    for (int i = 1; i < N; i++) pw[i] = (1ll * pw[i - 1] * Base) % MOD;
    // --------------------------------------------------------------
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", inp + i), a[inp[i] - 1] = i;
    for (int i = 0; i < m; i++) scanf("%d", b + i), h[i] = b[i];
    sort(h, h + m);
    for (int i = 0; i < m; i++) b[i] = lower_bound(h, h + m, b[i]) - h, p[b[i]] = i;
    for (int i = 0; i < n; i++) Hash = (1ll * Hash * Base + a[i]) % MOD;
    // --------------------------------------------------------------
    int CurHash = 0;
    for (int i = 0; i < m; i++) {
        if (i >= n) {
            CurHash -= (1ll * get_fen(b[i - n] - 1) * pw[n-1] + Get(b[i - n] + 1, m)) % MOD;
            if (CurHash < 0) CurHash += MOD;
            add_fen(b[i - n], -1), Set(b[i - n], 0);
        }
        apply(1, 1);
        CurHash = (1ll * CurHash * Base + get_fen(b[i]) + Get(b[i], m)) % MOD;
        add_fen(b[i], 1), Set(b[i], 1);
        if (i >= n - 1) if (CurHash == Hash) ans.push_back(i - n + 2);
    }
    printf("%d\n", ans.size());
    for (int i : ans) printf("%d ", i);

    return 0;
}

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:72:30: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n", ans.size());
                    ~~~~~~~~~~^
mat.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
mat.cpp:54:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 0; i < n; i++) scanf("%d", inp + i), a[inp[i] - 1] = i;
                                 ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
mat.cpp:55:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 0; i < m; i++) scanf("%d", b + i), h[i] = b[i];
                                 ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

• 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: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10