Submission #347257

#	Time	Username	Problem	Language	Result	Execution time	Memory
347257		Harry464	Matching (CEOI11_mat)	C++14	63 / 100	773 ms	65540 KiB

mat

#include <iostream>
#include <vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <set>

using namespace std;

typedef long long ll;

ll mod = 1000000007;

ll n, m;

vector <ll> fen(1000001,0);
vector <ll> brojevi(1000001,0);

ll sum(ll k){
  ll s = 0;
  while (k >= 1){
    s += fen[k];
    s %= mod;
    k -= k&-k;
  }
  return s;
}

void add(ll k, ll x){
  while (k <= m){
     fen[k] += x;
     k += k&-k;
  }
}

ll sum2(ll k){
  ll s = 0;
  while (k >= 1){
    s += brojevi[k];
    k -= k&-k;
  }
  return s;
}

void add2(ll k, ll x){
  while (k <= m){
     brojevi[k] += x;
     k += k&-k;
  }
}

int main()
{
    cin >> n >> m;
    vector <ll> a(n);
    vector <ll> b(m);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];
    vector <ll> t = a;
    for (int i = 0; i < n; i++)
        a[t[i]-1] = i + 1;
    map <ll, ll> key;
    vector <ll> k = b;
    sort(k.begin(), k.end());
    for (int i = 0; i < m; i++)
        key[k[i]] = i + 1;
    for (int i = 0; i < m; i++)
        b[i] = key[b[i]];
    ll poredi = 0;
    vector <ll> pows(1,1);
    for (int i = 1; i <= 1000000; i++)
        pows.push_back((pows[i-1]*67)%mod);
    for (int i = 0; i < n; i++)
        poredi += (a[i]*pows[i])%mod, poredi %= mod;
    ll hes = 0;
    set <ll> tren;
    for (int i = 0; i < n; i++)
        add2(b[i],1);
    vector <ll> rjesenja;
    for (int i = 0; i < n; i++){
        add(b[i], pows[i]);
        ll val = sum2(b[i]);
        hes += (val*pows[i])%mod, hes %= mod;
    }
    if (hes == poredi)
        rjesenja.push_back(1);
    for (int i = n; i < m; i++){
        poredi *= 67, poredi %= mod;
        ll o1 = sum(m) - sum(b[i-n]);
        while (o1 < 0)
            o1 += mod;
        ll o2 = (sum2(b[i-n])*pows[i-n])%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]);
        ll d1 = (sum2(b[i])*pows[i])%mod;
        ll d2 = sum(m) - sum(b[i]);
        while (d2 < mod)
            d2 += mod;
        hes += (d1 + d2)%mod;
        hes %= mod;
        hes -= (o1 + o2)%mod;
        while (hes < 0)
            hes += mod;
        hes %= mod;
        //cout << poredi << " " << hes << endl;
        if (poredi == hes)
            rjesenja.push_back(i - n + 2);
    }
    cout << rjesenja.size() << endl;
    for (int i = 0; i < rjesenja.size(); i++)
        cout << rjesenja[i] << " ";
}

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:114:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for (int i = 0; i < rjesenja.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