Submission #1137282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137282		HasanV11010238	Matching (CEOI11_mat)	C++20	63 / 100	1407 ms	80004 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;
}
int tr[4000004], lz[4000004];
struct SegTree{
    SegTree(int n){
    }
    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 f[1000001];
struct Fenwick{
    int n;
    Fenwick(int n){
        this->n = n;
    }
    void update(int x, int val){
        for (; x <= n; x = (x | (x + 1))){
            f[x] += val;
        }
    }
    int query(int r){
        int res = 0;
        for (; r > 0; r = (r & (r + 1)) - 1){
            res += f[r];
        }
        return res;
    }
};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n, m, a, ha = 0, pr = 0, invp;
    cin>>n>>m;
    vector<int> v(m + 1, 0);
    vector<vector<int>> so;
    for (int i = 0; i < n; i++){
        pr += 1LL * binpow(p, i);
        pr %= mod;
    }
    invp = binpow(p, mod - 2);
    for (int i = 0; i < n; i++){
        cin>>a;
        ha += 1LL * binpow(p, 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 tre(m);
    Fenwick cnt(m);
    for (ll i = 1; i <= n; i++){
        tre.update(1, 1, m, v[i], m, p);
        int coun = cnt.query(v[i]);
        cnt.update(v[i], 1);
        tre.put(1, 1, m, v[i], (i * binpow(p, coun)) % mod);
    }
    if (tr[1] == ha){
        ans.push_back(1);
    }
    for (ll i = n + 1; i <= m; i++){
        ll la = i - n;
        tre.put(1, 1, m, v[la], 0);
        tre.update(1, 1, m, v[la], m, invp);
        tre.update(1, 1, m, v[i], m, p);
        cnt.update(v[la], -1);
        int coun = cnt.query(v[i]);
        cnt.update(v[i], 1);
        tre.put(1, 1, m, v[i], (i * binpow(p, coun)) % mod);
        ha = (ha + pr) % mod;
        if (ha == 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