Submission #1137246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137246		HasanV11010238	Matching (CEOI11_mat)	C++20	63 / 100	2021 ms	110564 KiB

mat

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define MAX 1000000
#define p 1991213
#define mod 1000000007
using namespace std;
ll binpow(ll a, ll b){
    ll res = 1;
    while (b != 0){
        if (b % 2 == 0){
            b /= 2;
            a *= a;
            a %= mod;
        }
        else{
            b--;
            res *= a;
            res %= mod;
        }
    }
    return res;
}
struct SegTree{
    vector<int> tr, lz;
    SegTree(int n){
        tr.assign(4 * n + 4, 0), lz.assign(4 * n + 4, 1);
    }
    void relax(int v, int l, int r){
        tr[v] = (1LL * tr[v] * lz[v]) % mod;
        if (l != r){
            lz[v * 2] = (1LL * lz[v * 2] * lz[v]) % mod;
            lz[v * 2 + 1] = (1LL * lz[v * 2 + 1] * lz[v]) % mod;
        }
        lz[v] = 1;
    }
    ll put(int v, int l, int r, int pos, ll val){
        relax(v, l, r);
        if (l == r){
            ll va = val - tr[v];
            tr[v] = val;
            return va;
        }
        ll va;
        int mid = (l + r) / 2;
        if (pos <= mid){
            va = put(v * 2, l, mid, pos, val);
        }
        else{
            va = put(v * 2 + 1, mid + 1, r, pos, val);
        }
        tr[v] = (tr[v] + va + mod) % mod;
        return va;
    }
    void update(int v, int l, int r, int ql, int qr, ll val){
        relax(v, l, r);
        if (l > qr || r < ql){
            return;
        }
        if (ql <= l && r <= qr){
            lz[v] = (lz[v] * val) % mod;
            relax(v, l, r);
            return;
        }
        int mid = (l + r) / 2;
        update(v * 2, l, mid, ql, qr, val);
        update(v * 2 + 1, mid + 1, r, ql, qr, val);
        tr[v] = (tr[v * 2] + tr[v * 2 + 1]) % mod;
    }
    ll query(int v, int l, int r, int ql, int qr){
        relax(v, l, r);
        if (l > qr || r < ql){
            return 0;
        }
        if (ql <= l && r <= qr){
            return tr[v];
        }
        int mid = (l + r) / 2;
        return (query(v * 2, l, mid, ql, qr) + query(v * 2 + 1, mid + 1, r, ql, qr)) % mod;
    }
};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n, m, a, ha = 0, pr = 1, invp;
    cin>>n>>m;
    vector<int> v(m + 1, 0), pp(m + 1, 1);
    vector<vector<int>> so;
    for (int i = 1; i <= m; i++){
        pp[i] = (1LL * pp[i - 1] * p) % mod;
        if (i < n){
            pr += pp[i];
            pr %= mod;
        }
    }
    invp = binpow(p, mod - 2);
    for (int i = 0; i < n; i++){
        cin>>a;
        ha += pp[i] * a;
        ha %= mod;
    }
    for (int i = 1; i <= m; i++){
        cin>>v[i];
        so.push_back({(int)v[i], i});
    }
    sort(so.begin(), so.end());
    for (int i = 0; i < m; i++){
        v[so[i][1]] = i + 1;
    }
    vector<int> ans;
    so.clear();
    SegTree cnt(m), tr(m);
    for (ll i = 1; i <= n; i++){
        tr.update(1, 1, m, v[i], m, p);
        int coun = cnt.query(1, 1, m, 1, v[i]);
        cnt.put(1, 1, m, v[i], 1);
        tr.put(1, 1, m, v[i], (i * pp[coun]) % mod);
    }
    if (tr.tr[1] == ha){
        ans.push_back(1);
    }
    for (ll i = n + 1; i <= m; i++){
        ll la = i - n;
        tr.put(1, 1, m, v[la], 0);
        tr.update(1, 1, m, v[la], m, invp);
        tr.update(1, 1, m, v[i], m, p);
        cnt.put(1, 1, m, v[la], 0);
        int coun = cnt.query(1, 1, m, 1, v[i]);
        cnt.put(1, 1, m, v[i], 1);
        tr.put(1, 1, m, v[i], (i * pp[coun]) % mod);
        ha = (ha + pr) % mod;
        if (ha == tr.tr[1]){
            ans.push_back(la + 1);
        }
    }
    cout<<ans.size()<<"\n";
    for (int i = 0; i < (int)ans.size(); i++){
        cout<<ans[i]<<" ";
    }
    if (ans.size() == 0) cout<<"\n";
}

• 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