Submission #117642

#	Time	Username	Problem	Language	Result	Execution time	Memory
117642		JohnTitor	Matching (CEOI11_mat)	C++11	100 / 100	801 ms	40472 KiB

mat

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define setbit(s, i) (s|=(1LL<<(i)))
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
using ll=long long;
using ld=long double;
template <typename T> inline void read(T &x){
    char c;
    bool nega=0;
    while((!isdigit(c=getchar()))&&(c!='-'));
    if(c=='-'){
        nega=1;
        c=getchar();
    }
    x=c-48;
    while(isdigit(c=getchar())) x=x*10+c-48;
    if(nega) x=-x;
}
template <typename T> inline void writep(T x){
    if(x>9) writep(x/10);
    putchar(x%10+48);
}
template <typename T> inline void write(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    writep(x);
}
template <typename T> inline void writeln(T x){
    write(x);
    putchar('\n');
}
#define taskname "Matching"
int n, m;
int a[1000002];
int b[1000002];
namespace KMP_log{
    int f[1000002];
    int ft[1000002];
    int pos[1000002];
    void update(int u, int x){
        for(; u<=1000000; u+=u&-u) ft[u]+=x;
    }
    int get(int u){
        int res=0;
        for(; u>0; u-=u&-u) res+=ft[u];
        return res;
    }
    void solve(){
        FOR(i, 1, n){
            pos[i]=get(a[i]);
            update(a[i], 1);
        }
        pos[n+1]=-1;
        FOR(i, 0, 1000000) ft[i]=0;
        int p=0;
        FOR(i, 2, n){
            while(p&&(get(a[i])!=pos[p+1])){
                int nx=f[p];
                while(p>nx){
                    update(a[i-p], -1);
                    p--;
                }
            }
            p++;
            f[i]=p;
            update(a[i], 1);
        }
        FOR(i, 0, 1000000) ft[i]=0;
        p=0;
        vector <int> ans;
        FOR(i, 1, m){
            while(p&&get(b[i])!=pos[p+1]){
                int nx=f[p];
                while(p>nx){
                    update(b[i-p], -1);
                    p--;
                }
            }
            p++;
            if(p==n) ans.pb(i-n+1);
            update(b[i], 1);
        }
        writeln(ans.size());
        for(int x: ans){
            write(x);
            putchar(' ');
        }
    }
};
ll f;
map <int, int> M;
int main(){
    #ifdef Uiharu
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Uiharu
    read(n);
    read(m);
    FOR(i, 1, n){
        int temp;
        read(temp);
        a[temp]=i;
    }
    vector <int> cont;
    FOR(i, 1, m){
        read(b[i]);
        cont.push_back(b[i]);
    }
    sort(cont.begin(), cont.end());
    FOR(i, 1, m) b[i]=lower_bound(cont.begin(), cont.end(), b[i])-cont.begin()+1;
//    FOR(i, 1, m) cerr<<b[i]<<" \n"[i==m];
    KMP_log::solve();
}

• 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