oj.uz

Submission #347260

# Submission time Handle Problem Language Result Execution time Memory
347260 2021-01-12T12:49:53 Z Harry464 Matching (CEOI11_mat) C++14
100 / 100
 1311 ms 65536 KB 
#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 <int> 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;
  }
}

int sum2(int k){
  int 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;
    vector <pair <ll,ll> > k(m);
    for (int i = 0; i < m; i++)
        k[i].first = b[i], k[i].second = i;
    sort(k.begin(), k.end());
    for (int i = 0; i < m; i++)
        b[k[i].second] = i + 1;
    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

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 20440 KB Output is correct
2 Correct 28 ms 20440 KB Output is correct
3 Correct 31 ms 20440 KB Output is correct
4 Correct 29 ms 20440 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 20440 KB Output is correct
2 Correct 33 ms 20440 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 20952 KB Output is correct
2 Correct 42 ms 20952 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 20952 KB Output is correct
2 Correct 43 ms 20952 KB Output is correct
3 Correct 31 ms 20440 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 25232 KB Output is correct
2 Correct 206 ms 25048 KB Output is correct
3 Correct 242 ms 26072 KB Output is correct
4 Correct 241 ms 25976 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 26056 KB Output is correct
2 Correct 241 ms 25304 KB Output is correct
3 Correct 239 ms 25416 KB Output is correct
4 Correct 211 ms 29512 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 26312 KB Output is correct
2 Correct 202 ms 25816 KB Output is correct
3 Correct 240 ms 25432 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1187 ms 58440 KB Output is correct
2 Correct 1288 ms 65536 KB Output is correct
3 Correct 1012 ms 46680 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1083 ms 57680 KB Output is correct
2 Correct 1311 ms 50648 KB Output is correct
3 Correct 1170 ms 65536 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1111 ms 54464 KB Output is correct
2 Correct 1047 ms 64956 KB Output is correct
3 Correct 1236 ms 54488 KB Output is correct
4 Correct 1018 ms 65536 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1074 ms 55624 KB Output is correct
2 Correct 1203 ms 55128 KB Output is correct
3 Correct 505 ms 37848 KB Output is correct
4 Correct 1119 ms 65536 KB Output is correct