Submission #347388

#	Time	Username	Problem	Language	Result	Execution time	Memory
347388		Uncreative	Matching (CEOI11_mat)	C++14	100 / 100	1235 ms	46828 KiB

mat

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int mod = 1000000087;

int B = 1000033;

const int maxn = 1000010;

int s[maxn];
pair<int, int> h[maxn];

int a[maxn];

pair<int, int> c[maxn];
int d[maxn];

long long loga[2 * maxn];
int loga2[2 * maxn];

void update(int x, int val){
    for (; x < 2 * maxn; x += (x & (-x))){
        loga[x] += val;
        if (loga[x] < 0){
            loga[x] += mod;
        }
        loga[x] %= mod;
    }
}

int query(int x){
    int ret = 0;
    for (; x > 0; x -= (x & (-x))){
        ret += loga[x];
        ret %= mod;
    }
    return ret;
}

void update2(int x, int val){
    for (; x < 2 * maxn; x += (x & (-x))){
        loga2[x] += val;
    }
}

int query2(int x){
    int ret = 0;
    for (; x > 0; x -= (x & (-x))){
        ret += loga2[x];
    }
    return ret;
}


int pot(int e){
    if (e == 0){
        return 1;
    }
    if (e % 2 == 1){
        int t = ((long long)pot(e - 1) * (long long)B) % mod;
        return t;
    }
    if (e % 2 == 0){
        long long t = pot(e / 2);
        return ((t * t) % mod);
    }
}

int main(){
    int inv = pot(mod - 2);
    //cout << inv;
    int n, m;
    cin >> m >> n;
    for (int i = 1; i <= m; i++){
        int x;
        cin >> x;
        s[x] = i;
    }
    long long hs = 0;
    for (int i = 1; i <= m; i++){
        hs *= B;
        hs %= mod;
        hs += s[i];
        hs %= mod;
    }
    //cout << "HS " << hs << endl;
    for (int i = 1; i <= n; i++){
        int x;
        cin >> x;
        h[i] = make_pair(x, i);
    }

    sort(h + 1, h + n + 1);
    for (int i = 1; i <= n; i++){
        a[h[i].second] = i;
    }

    /*for (int i = 1; i <= n; i++){
        cout << a[i] << " ";
    }*/
    for (int i = 1; i <= m; i++){
        c[i] = make_pair(a[i], i);
    }
    sort(c + 1, c + m + 1);
    for (int i = 1; i <= m; i++){
        d[c[i].second] = i;
    }

    vector<int> sol;

    long long h2 = 0, bp = 1;
    for (int i = m; i >= 1; i--){
        update2(a[i], 1);
        h2 += (d[i] * bp);
        h2 %= mod;
        update(a[i], bp);
        bp *= B;
        bp %= mod;
        //cout << "T " << h2 << endl;
    }
    if (hs == h2){
        sol.push_back(1);
    }
    long long bm = 1;
    long long inb = inv;

    for (int i = m + 1; i <= n; i++){
        long long t = query(n) - query(a[i - m]);
        if (t < 0){
            t += mod;
        }
        t *= bm;
        t %= mod;
        h2 -= t;
        if (h2 < 0){
            h2 += mod;
        }
        h2 %= mod;
        t = query(a[i - m]) - query(a[i - m] - 1);
        if (t < 0){
            t += mod;
        }
        t %= mod;
        update(a[i - m], -t);
        t *= bm;
        t %= mod;
        t *= query2(a[i - m]);
        t %= mod;
        h2 -= t;
        if (h2 < 0){
            h2 += mod;
        }
        h2 %= mod;
        update2(a[i - m], -1);


        h2 *= B;
        h2 %= mod;
        bm *= B;
        bm %= mod;
        t = query(n) - query(a[i]);
        if (t < 0){
            t += mod;
        }
        t *= bm;
        t %= mod;
        h2 += t;
        h2 %= mod;
        update(a[i], inb);
        inb *= inv;
        inb %= mod;

        update2(a[i], 1);
        h2 += query2(a[i]);
        h2 %= mod;

        //cout << h2 << endl;
        if (h2 == hs){
            sol.push_back(i - m + 1);
        }
    }
    cout << sol.size() << "\n";
    for (int i = 0; i < sol.size(); i++){
        cout << sol[i] << " ";
    }
    if (sol.size() == 0){
        cout << "\n";
    }
}

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:186:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |     for (int i = 0; i < sol.size(); i++){
      |                     ~~^~~~~~~~~~~~
mat.cpp: In function 'int pot(int)':
mat.cpp:70:1: warning: control reaches end of non-void function [-Wreturn-type]
   70 | }
      | ^

• 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