Submission #374069

#	Time	Username	Problem	Language	Result	Execution time	Memory
374069		hhh07	Matching (CEOI11_mat)	C++14	63 / 100	974 ms	65540 KiB

mat

#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <climits>
#include <vector>
#include <utility>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> ii;

ll mod = 1e9 + 7, p = 1000003, n, m;
vector<ll> fen(1000001, 0);
vector<int> fen2(1000001, 0);

ll sum(ll idx){
    ll sum = 0;
    while(idx > 0){

        sum += fen[idx];
        sum %= mod;
        idx -= idx&-idx;
    }
    return sum;
}

void add(ll idx, ll val){
    while(idx <= m){
        fen[idx] += val;
        idx += idx&-idx;
    }
}
int sum2(int idx){
    int sum = 0;
    while(idx > 0){

        sum += fen2[idx];
        idx -= idx&-idx;
    }
    return sum;
}

void add2(int idx, int val){
    while(idx <= m){
        fen2[idx] += val;
        idx += idx&-idx;
    }
}

int main(){
    std::ios::sync_with_stdio(false);
    cin >> n >> m;
    vector<ll> a(n), b(m);
    
    for (int i = 0; i < n; i++)
        cin >> a[i];
    
    for (ll i = 0; i < m; i++)
        cin >> b[i];
    
    vector<ll> c = a;
    for (ll i = 0; i < n; i++)
        a[c[i] - 1] = i + 1;
    vector<ii> d;
    for (ll i = 0; i < m; i++)
        d.push_back({b[i], i});
    sort(d.begin(), d.end());
    for (ll i = 0; i < m; i++)
        b[d[i].second] = i + 1;
    
    ll hes = 0, hes2 = 0;
    vector<ll> pows;
    pows.push_back(1);
    for (ll i = 1; i < 1000001; i++)
        pows.push_back((pows[i - 1]*p)%mod);
    for (ll i = 0; i < n; i++){
        hes += pows[i]*a[i];
        hes %= mod;
        add2(b[i], 1);
    }
    vector<ll> rj;
    
    for (ll i = 0; i < n; i++){
        add(b[i], pows[i]);
        hes2 += (sum2(b[i])*pows[i])%mod;
        hes2 %= mod;
    }
    if (hes == hes2)
        rj.push_back(1);
    
    for (ll i = n; i < m; i++){
        hes *= p; hes %= mod;
        hes2 -= sum(m) - sum(b[i - n]) + (sum2(b[i - n])*pows[i - n])%mod;
        while(hes2 < 0)
            hes2 += mod;
        
        add2(b[i - n], -1);
        add(b
            [i - n], -sum(b[i - n]) + sum(b[i - n] - 1));
        add2(b[i], 1);
        add(b[i], pows[i]);
        hes2 += sum(m) - sum(b[i]) + (sum2(b[i])*pows[i])%mod;
        while(hes2 < 0)
            hes2 += mod;
        hes2 %= mod;
        if (hes == hes2)
            rj.push_back(i - n + 2);
    }
    cout << rj.size() << endl;
    for (ll i = 0; i < rj.size(); i++)
        cout << rj[i] << " ";
    
    
    return 0;
}

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:112:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for (ll i = 0; i < rj.size(); i++)
      |                    ~~^~~~~~~~~~~

• 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