Submission #1151461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151461		nathan4690	Matching (CEOI11_mat)	C++20	100 / 100	1452 ms	62456 KiB

mat

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define f1(i,n) for(int i=1;i<=n;i++)
#define __file_name ""
#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
using namespace std;
const ll maxn = 1e6+5, inf=1e18, mod=1e9+7;

struct Lazy{
    int data = 1;
    Lazy(){};
    Lazy(int data): data(data){};
    Lazy operator+(const Lazy &rhs) const{
        // Push a lazy down
        return Lazy(1LL * data * rhs.data % mod);
    }
};

struct Value{
    int data = 0;
    Value(){};
    Value(int data): data(data){};
    Value operator+(const Value &rhs) const{
        // Merge two nodes
        return Value((data + rhs.data) % mod);
    }
    Value operator+(const Lazy &rhs) const{
        // Apply lazy to node
        return Value(1LL * data * rhs.data % mod);
    }
};

template<class T, class U>
struct SegmentTree{
    int n;
    T st[4*maxn];
    U lazy[4*maxn];
    SegmentTree(){};
//    SegmentTree(int n): n(n), st(4*n+1), lazy(4*n+1){};
    void init(int n_){
        n = n_;
//        st.resize(4 * n + 1);
//        lazy.resize(4 * n + 1);
    };
    inline void down(int idx){
        st[idx*2] = st[idx*2] + lazy[idx];
        lazy[idx*2] = lazy[idx*2] + lazy[idx];
        st[idx*2+1] = st[idx*2+1] + lazy[idx];
        lazy[idx*2+1] = lazy[idx*2+1] + lazy[idx];
        lazy[idx] = U();
    }
    void _upd1(int idx, int l, int r, int i, const T &v){
        if(i < l || r < i) return;
        if(l == r){
            st[idx] = v;
            return;
        }
        down(idx);
        int mid = (l + r) / 2;
        _upd1(idx*2, l, mid, i, v);
        _upd1(idx*2+1, mid+1, r, i, v);
        st[idx] = st[idx*2] + st[idx*2+1];
    }
    inline void updatePoint(int position, const T &value){
        _upd1(1,1,n,position,value);
    }
    void _upd2(int idx, int l, int r, int u, int v, const U &w){
        if(v < l || r < u) return;
        if(u <= l && r <= v){
            st[idx] = st[idx] + w;
            lazy[idx] = lazy[idx] + w;
            return;
        }
        down(idx);
        int mid = (l + r) / 2;
        _upd2(idx*2, l, mid, u, v, w);
        _upd2(idx*2+1, mid+1, r, u, v, w);
        st[idx] = st[idx*2] + st[idx*2+1];
    }
    inline void updateRange(int left_, int right_, const U &value){
        _upd2(1,1,n,left_, right_, value);
    }
    T _get(int idx, int l, int r, int u, int v){
        if(v < l || r < u) return T();
        if(u <= l && r <= v) return st[idx];
        down(idx);
        int mid = (l + r) / 2;
        return _get(idx*2, l, mid, u, v) + _get(idx*2+1, mid+1, r, u, v);
    }
    inline T getRange(int left_, int right_){
        return _get(1,1,n,left_, right_);
    }
};

#define SegTree SegmentTree<Value, Lazy>

struct FenwickTree{
    int n;
    int bit[maxn];
    FenwickTree(){}
//    FenwickTree(int n): n(n), bit(n+1){}
    void init(int n_){
        n = n_;
//        bit.resize(n + 1);
    }
    void update(int idx, long long v){
        if(idx <= 0) return;
        for(;idx<=n;idx+=(idx&-idx)) bit[idx]+=v;
    }
    int getSum(int idx){
        if(idx <= 0) return 0;
        int res = 0;
        for(;idx;idx-=idx&-idx) res += bit[idx];
        return res;
    }
};

ll powmod(ll base, ll e){
    ll res = 1;
    while(e){
        if(e & 1) res = res * base % mod;
        base = base * base % mod;
        e >>= 1;
    }
    return res;
}

int n, k, p[maxn], a[maxn];
vector<int> all;
ll base, invbase, pw[maxn];
SegTree st;
FenwickTree bit;
vector<int> ans;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp","r",stdin);
        freopen(__file_name ".out","w",stdout);
    }
    // code here
//    scanf("%d%d", &k, &n);
    scan(k); scan(n);
    f1(i,k) scan(p[i]);
    f1(i,n) {
        scan(a[i]);
        all.push_back(a[i]);
    }
    sort(all.begin(), all.end());
    f1(i,n) a[i] = lower_bound(all.begin(), all.end(), a[i]) - all.begin() + 1;
    base = n + 1; invbase = powmod(base, mod - 2);
    ll curmult = 1, hashP = 0, incP = 0;
    bit.init(n);
    st.init(n);
    f1(i,k){
        hashP = (hashP + curmult * p[i]) % mod;
        incP = (incP + curmult) % mod;
        curmult = (curmult * base) % mod;
        bit.update(a[i], 1);
    }
    pw[0] = 1;
    f1(i, n) pw[i] = pw[i-1] * base % mod;
    f1(i,k){
        int cbase = bit.getSum(a[i] - 1);
        st.updatePoint(a[i], pw[cbase] * i % mod);
    }
    if(st.st[1].data == hashP){
        ans.push_back(1);
    }
    for(int i=1;i+k<=n;i++){
        hashP = (hashP + incP) % mod;
        st.updateRange(a[i], n, invbase);
        bit.update(a[i], -1);
        st.updatePoint(a[i], 0);
        int j = i + k;
        bit.update(a[j], 1);
        st.updatePoint(a[j], pw[bit.getSum(a[j] - 1)] * j % mod);
        st.updateRange(a[j]+1,n,base);
        if(st.st[1].data == hashP){
            ans.push_back(i + 1);
        }
    }
    printf("%d\n",(int)ans.size());
    for(int item: ans) printf("%d ", item);
    return 0;
}

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         freopen(__file_name ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mat.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         freopen(__file_name ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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