Submission #475590

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
475590	2021-09-23T05:58:13 Z	stefantaga	Matching (CEOI11_mat)	C++14	100 / 100	1485 ms	62324 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 && val2 == hash2)
            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;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	1484 KB	Output is correct
2	Correct	16 ms	1368 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	1484 KB	Output is correct
2	Correct	18 ms	1412 KB	Output is correct
3	Correct	4 ms	460 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	177 ms	9928 KB	Output is correct
2	Correct	193 ms	10208 KB	Output is correct
3	Correct	278 ms	10380 KB	Output is correct
4	Correct	262 ms	10484 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	213 ms	10784 KB	Output is correct
2	Correct	262 ms	10288 KB	Output is correct
3	Correct	209 ms	10708 KB	Output is correct
4	Correct	214 ms	12512 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	222 ms	10760 KB	Output is correct
2	Correct	241 ms	10272 KB	Output is correct
3	Correct	214 ms	10352 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1228 ms	55168 KB	Output is correct
2	Correct	1485 ms	60956 KB	Output is correct
3	Correct	1095 ms	47820 KB	Output is correct

Subtask #9
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1273 ms	53668 KB	Output is correct
2	Correct	1424 ms	51212 KB	Output is correct
3	Correct	1354 ms	57684 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1186 ms	53388 KB	Output is correct
2	Correct	1109 ms	62324 KB	Output is correct
3	Correct	1339 ms	53824 KB	Output is correct
4	Correct	1070 ms	58908 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1154 ms	53856 KB	Output is correct
2	Correct	1275 ms	54844 KB	Output is correct
3	Correct	510 ms	26588 KB	Output is correct
4	Correct	1154 ms	59460 KB	Output is correct

Submission #475590

Compilation message