# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
132709 |
2019-07-19T11:35:57 Z |
pavel |
Matching (CEOI11_mat) |
C++14 |
|
1645 ms |
27696 KB |
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 1000006;
const int MAXM = 1000006;
const int MOD = 1000000007;
const int BASE = 1000006;
typedef long long ll;
int ADD(ll a, ll b){
return (a+b)%MOD;
}
int SUB(ll a, ll b){
return (a-b+MOD)%MOD;
}
int MUL(ll a, ll b){
return a*b%MOD;
}
int EXP(ll a, int e){
if(e==0) return 1;
if(e%2) return MUL(a, EXP(a, e-1));
else return EXP(MUL(a, a), e/2);
}
int DIV(ll a, ll b){
return MUL(a, EXP(b, MOD-2));
}
int n,m;
int p[MAXN], h[MAXM], hs[MAXN], f1[MAXM], f2[MAXM], pot[MAXN];
int hsh=0, sld=0, bb=1;
vector<int> sol;
void fadd(int* fen,int idx, int v){
for(idx++;idx<MAXM;idx+=idx&-idx){
fen[idx]=ADD(fen[idx], v);
}
}
int fquery(int* fen, int idx){
int r=0;
for(idx++;idx>0;idx-=idx&-idx){
r=ADD(r, fen[idx]);
}
return r;
}
void add_idx(int i){
sld=ADD(sld, MUL(bb, SUB(fquery(f1, MAXM-2), fquery(f1, h[i]))));
sld=MUL(sld, BASE);
sld=ADD(sld, fquery(f2, h[i])+1);
bb=MUL(bb, BASE);
fadd(f1, h[i], DIV(1, bb));
fadd(f2, h[i], 1);
}
void rem_idx(int i){
sld=SUB(sld, MUL(fquery(f2, h[i]), EXP(BASE, n)));
sld=SUB(sld, MUL(bb, SUB(fquery(f1, MAXM-2), fquery(f1, h[i]))));
fadd(f1, h[i], -(fquery(f1, h[i])-(h[i]?fquery(f1, h[i]-1):0)));
fadd(f2, h[i], -1);
}
int main(){
scanf("%d%d", &n, &m);
for(int i=0;i<n;++i){
int x;
scanf("%d", &x);
p[x-1]=i+1;
}
for(int i=0;i<n;++i){
hsh=ADD(MUL(hsh, BASE), p[i]);
}
for(int i=0;i<m;++i){
scanf("%d", &h[i]);
hs[i]=h[i];
}
sort(hs, hs+m);
for(int i=0;i<m;++i){
h[i]=lower_bound(hs, hs+m, h[i])-hs;
}
for(int i=0;i<n;++i){
add_idx(i);
}
if(sld==hsh) sol.push_back(1);
for(int i=n;i<m;++i){
add_idx(i);
rem_idx(i-n);
if(sld==hsh) sol.push_back(i-n+2);
}
printf("%d\n", (int)sol.size());
for(auto i:sol){
printf("%d ", i);
}
puts("");
}
Compilation message
mat.cpp: In function 'int main()':
mat.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
mat.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
mat.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &h[i]);
~~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
504 KB |
Output is correct |
2 |
Correct |
3 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
888 KB |
Output is correct |
2 |
Correct |
22 ms |
888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
932 KB |
Output is correct |
2 |
Correct |
24 ms |
888 KB |
Output is correct |
3 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
209 ms |
3716 KB |
Output is correct |
2 |
Correct |
221 ms |
3952 KB |
Output is correct |
3 |
Correct |
286 ms |
4176 KB |
Output is correct |
4 |
Correct |
288 ms |
4132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
245 ms |
4520 KB |
Output is correct |
2 |
Correct |
312 ms |
3972 KB |
Output is correct |
3 |
Correct |
242 ms |
4344 KB |
Output is correct |
4 |
Correct |
229 ms |
6276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
231 ms |
4472 KB |
Output is correct |
2 |
Correct |
222 ms |
4108 KB |
Output is correct |
3 |
Correct |
264 ms |
4016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1347 ms |
18380 KB |
Output is correct |
2 |
Correct |
1514 ms |
20636 KB |
Output is correct |
3 |
Correct |
1420 ms |
13432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1233 ms |
17196 KB |
Output is correct |
2 |
Correct |
1645 ms |
16888 KB |
Output is correct |
3 |
Correct |
1515 ms |
20772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1345 ms |
17848 KB |
Output is correct |
2 |
Correct |
1153 ms |
27696 KB |
Output is correct |
3 |
Correct |
1480 ms |
16632 KB |
Output is correct |
4 |
Correct |
930 ms |
20856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1277 ms |
18420 KB |
Output is correct |
2 |
Correct |
1425 ms |
17272 KB |
Output is correct |
3 |
Correct |
623 ms |
9464 KB |
Output is correct |
4 |
Correct |
1159 ms |
20288 KB |
Output is correct |