이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
const int N = 1000100;
const lli MOD=1e9+7;
int t, n, m, br=-1;
lli a[N], b[N], d;
vector<lli>v, poc, sol;
lli f[N], active[N];
lli B=32452867, hesh, sub;
lli pot[N], upd;
lli powmod (lli a, lli x) {
lli rez=1;
while (x) {
if (x%2) {
rez = ((rez%MOD)*(a%MOD))%MOD;
}
a = ((a%MOD)*(a%MOD))%MOD;
x/=2;
}
return rez;
}
lli divide (lli a, lli b) {
return a * powmod(b, MOD-2) % MOD;
}
lli sum (int x) {
if (!x) return 0;
lli zbr=0;
for (; x > 0; x-=(x&-x)) zbr+=f[x];
return zbr;
}
void update (int x, int val) {
for (; x < N; x+=(x&-x)) f[x]+=val;
return;
}
int kol (int x) {
if (!x) return 0;
lli zbr=0;
for (; x > 0; x-=(x&-x)) zbr+=active[x];
return zbr;
}
void update_active (int x, int val) {
for (; x < N; x+=(x&-x)) active[x]+=val;
return;
}
void sazmi () {
sort (v.begin(), v.end());
for (int i = 1; i <= m; i++) {
b[i] = lower_bound(v.begin(), v.end(), b[i])-v.begin()+1;
if (i <= n) poc.push_back(b[i]);
}
sort (poc.begin(), poc.end());
for (int i = 1; i <= n; i++) {
lli val = lower_bound(poc.begin(), poc.end(), b[i])-poc.begin()+1;
if (i==1) hesh=val;
else hesh=(hesh*B%MOD+val)%MOD;
update(b[i], divide(1, pot[upd]));
upd++;
update_active(b[i], 1);
}
return;
}
void solve () {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> d;
a[d]=i;
}
br=m-1;
upd=0;
pot[0]=1;
for (int i = 1; i <= m; i++) {
cin >> b[i];
v.push_back(b[i]);
pot[i]=(pot[i-1]*B)%MOD;
}
hesh=0;
sazmi ();
//for (int i = 1; i <= n; i++) cout << a[i] << " ";
for (int i = 1; i <= n; i++) {
if (i==1) sub=a[i];
else sub=((sub*B+a[i])%MOD)%MOD;
}
if (sub == hesh) sol.push_back(1);
//cout << sub << " " << hesh << endl;
for (int i = n+1; i <= m; i++) {
lli dod = sum(N-5)-sum(b[i]);
dod=(dod*pot[upd-1]%MOD);
lli kolikoManjih = kol(b[i]);
hesh = ((hesh+dod)*B%MOD+kolikoManjih+1)%MOD;
/*for (int j = 1; j < N; j++) {
if (sum(j)-sum(j-1)) cout << j << " " << (sum(j)-sum(j-1))*pot[upd-1]%MOD << endl;
}
cout << upd << " " << sum(N-5)*pot[upd-1]%MOD << endl;*/
update_active(b[i], 1);
update(b[i], divide(1, pot[upd]));
upd++;
int last = i-n;
kolikoManjih = kol(b[last]);
hesh = (hesh-kolikoManjih*pot[n]%MOD)%MOD;
lli makni = sum(b[last])-sum(b[last]-1);
update (b[last], -makni);
update_active (b[last], -1);
dod = sum(N-5)-sum(b[last]);
dod = (dod*pot[upd-1])%MOD;
hesh = ((hesh-dod)%MOD+MOD)%MOD;
if (hesh==sub) sol.push_back(i-n+1);
}
cout << sol.size() << "\n";
for (int i = 0; i < sol.size(); i++) cout << sol[i] << " ";
return;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
/*
5 9
1 4 2 3 5
1 4 5 2 6 8 11 7 16
5 8
1 4 2 3 5
1 4 5 2 6 8 7 11
*/
컴파일 시 표준 에러 (stderr) 메시지
mat.cpp: In function 'void solve()':
mat.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for (int i = 0; i < sol.size(); i++) cout << sol[i] << " ";
| ~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |