oj.uz

Submission #739144

# Submission time Handle Problem Language Result Execution time Memory
739144 2023-05-10T03:44:58 Z huynhyen1609 Matching (CEOI11_mat) C++14
100 / 100
 1204 ms 62104 KB 
#include <bits/stdc++.h>
#define DIM 1000010
#define MOD1 1000000007
#define MOD2 1000000009
#define B 10000
using namespace std;
 
struct segment_tree{
    int hash1,hash2;
    int cnt;
} aint[DIM*4];
 
pair <int,int> v[DIM];
int nrm[DIM];
int p1[DIM],p2[DIM];
vector <int> sol;
int n,m,i,j,x;
 
void update (int nod, int st, int dr, int poz, int val){
    if (st == dr){
        aint[nod].hash1 = aint[nod].hash2 = val;
        if (val)
            aint[nod].cnt = 1;
        else aint[nod].cnt = 0;
 
        return;
    }
    int mid = (st+dr)>>1;
    if (poz <= mid)
        update (nod<<1,st,mid,poz,val);
    else update ((nod<<1)|1,mid+1,dr,poz,val);
 
    int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
 
    aint[nod].hash1 = (1LL * aint[fiu_st].hash1 * p1[ aint[fiu_dr].cnt ] % MOD1 + aint[fiu_dr].hash1) % MOD1;
    aint[nod].hash2 = (1LL * aint[fiu_st].hash2 * p2[ aint[fiu_dr].cnt ] % MOD2 + aint[fiu_dr].hash2) % MOD2;
    aint[nod].cnt = aint[fiu_st].cnt + aint[fiu_dr].cnt;
}
 
 
int main (){
 
    //ifstream cin ("date.in");
    //ofstream cout ("date.out");
 
    cin>>m>>n;
 
    int hash1 = 0, hash2 = 0;
    for (i=1;i<=m;i++){
        cin>>x;
        hash1 = (1LL * hash1 * B % MOD1 + x) % MOD1;
        hash2 = (1LL * hash2 * B % MOD2 + x) % MOD2;
    }
 
    p1[0] = p2[0] = 1;
    for (i=1;i<=n;i++){
        p1[i] = 1LL * p1[i-1] * B % MOD1;
        p2[i] = 1LL * p2[i-1] * B % MOD2;
    }
 
    for (i=1;i<=n;i++){
        cin>>v[i].first;
        v[i].second = i;
    }
 
    sort (v+1,v+n+1);
    for (i=1;i<=n;i++)
        nrm[v[i].second] = i;
 
    for (i=1;i<m;i++)
        update (1,1,n,nrm[i],i);
 
    int sum1 = 0, sum2 = 0;
    for (i=0;i<m;i++){
        sum1 = (sum1 + p1[i]) % MOD1;
        sum2 = (sum2 + p2[i]) % MOD2;
    }
 
    for (i=m;i<=n;i++){
        /// adaug elem asta
        update (1,1,n,nrm[i],i);
 
        int val1 = (aint[1].hash1 - 1LL * sum1 * (i-m) % MOD1 + MOD1) % MOD1;
        int val2 = (aint[1].hash2 - 1LL * sum2 * (i-m) % MOD2 + MOD2) % MOD2;
        if (val1 == hash1)
            sol.push_back(i-m+1);
 
        /// sterg i-m+1
        update (1,1,n,nrm[i-m+1],0);
    }
 
    cout<<sol.size()<<"\n";
    for (auto it : sol)
        cout<<it<<" ";
 
    return 0;
}

Compilation message

mat.cpp: In function 'int main()':
mat.cpp:84:13: warning: unused variable 'val2' [-Wunused-variable]
   84 |         int val2 = (aint[1].hash2 - 1LL * sum2 * (i-m) % MOD2 + MOD2) % MOD2;
      |             ^~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 308 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1548 KB Output is correct
2 Correct 15 ms 1604 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1676 KB Output is correct
2 Correct 16 ms 1544 KB Output is correct
3 Correct 3 ms 452 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 10664 KB Output is correct
2 Correct 160 ms 11440 KB Output is correct
3 Correct 220 ms 12596 KB Output is correct
4 Correct 219 ms 12564 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 11472 KB Output is correct
2 Correct 226 ms 12308 KB Output is correct
3 Correct 182 ms 12668 KB Output is correct
4 Correct 173 ms 13760 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 11528 KB Output is correct
2 Correct 172 ms 11844 KB Output is correct
3 Correct 188 ms 12216 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 992 ms 45888 KB Output is correct
2 Correct 1204 ms 60936 KB Output is correct
3 Correct 943 ms 47772 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 919 ms 44288 KB Output is correct
2 Correct 1157 ms 51232 KB Output is correct
3 Correct 1129 ms 57676 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 993 ms 46220 KB Output is correct
2 Correct 897 ms 62104 KB Output is correct
3 Correct 1151 ms 53804 KB Output is correct
4 Correct 897 ms 58880 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 950 ms 46460 KB Output is correct
2 Correct 1061 ms 54656 KB Output is correct
3 Correct 440 ms 26636 KB Output is correct
4 Correct 982 ms 59408 KB Output is correct