oj.uz

Submission #374067

# Submission time Handle Problem Language Result Execution time Memory
374067 2021-03-06T14:15:09 Z hhh07 Matching (CEOI11_mat) C++14
63 / 100
 924 ms 65540 KB 
#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;
ll fen[1000001];
int fen2[1000001];

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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 8672 KB Output is correct
2 Correct 22 ms 8668 KB Output is correct
3 Correct 23 ms 8668 KB Output is correct
4 Correct 23 ms 8672 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 8792 KB Output is correct
2 Correct 26 ms 8676 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 9176 KB Output is correct
2 Correct 31 ms 9180 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 9304 KB Output is correct
2 Correct 32 ms 9180 KB Output is correct
3 Correct 24 ms 8792 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 15312 KB Output is correct
2 Correct 140 ms 15296 KB Output is correct
3 Correct 147 ms 16220 KB Output is correct
4 Correct 142 ms 16220 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 16716 KB Output is correct
2 Correct 152 ms 15440 KB Output is correct
3 Correct 149 ms 15952 KB Output is correct
4 Correct 136 ms 20180 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 16848 KB Output is correct
2 Correct 120 ms 15952 KB Output is correct
3 Correct 158 ms 15696 KB Output is correct

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 718 ms 55612 KB Output is correct
2 Runtime error 461 ms 65540 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 647 ms 54788 KB Output is correct
2 Correct 924 ms 51900 KB Output is correct
3 Runtime error 416 ms 65540 KB Execution killed with signal 9

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 731 ms 52992 KB Output is correct
2 Correct 652 ms 65536 KB Output is correct
3 Correct 801 ms 57788 KB Output is correct
4 Runtime error 387 ms 65540 KB Execution killed with signal 9

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 678 ms 53876 KB Output is correct
2 Correct 789 ms 52796 KB Output is correct
3 Correct 301 ms 27464 KB Output is correct
4 Runtime error 481 ms 65540 KB Execution killed with signal 9