# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
132711 |
2019-07-19T11:43:37 Z |
pavel |
Matching (CEOI11_mat) |
C++14 |
|
1661 ms |
27064 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 = 1000066;
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 |
504 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
760 KB |
Output is correct |
2 |
Correct |
21 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
760 KB |
Output is correct |
2 |
Correct |
24 ms |
760 KB |
Output is correct |
3 |
Correct |
5 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
209 ms |
3312 KB |
Output is correct |
2 |
Correct |
222 ms |
3424 KB |
Output is correct |
3 |
Correct |
344 ms |
3800 KB |
Output is correct |
4 |
Correct |
291 ms |
3832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
255 ms |
4172 KB |
Output is correct |
2 |
Correct |
357 ms |
3584 KB |
Output is correct |
3 |
Correct |
284 ms |
3940 KB |
Output is correct |
4 |
Correct |
262 ms |
5792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
231 ms |
4084 KB |
Output is correct |
2 |
Correct |
226 ms |
3832 KB |
Output is correct |
3 |
Correct |
263 ms |
3576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1338 ms |
17708 KB |
Output is correct |
2 |
Correct |
1551 ms |
19960 KB |
Output is correct |
3 |
Correct |
1251 ms |
12856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1230 ms |
16524 KB |
Output is correct |
2 |
Correct |
1661 ms |
16032 KB |
Output is correct |
3 |
Correct |
1496 ms |
19724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1377 ms |
17176 KB |
Output is correct |
2 |
Correct |
1187 ms |
27064 KB |
Output is correct |
3 |
Correct |
1479 ms |
16112 KB |
Output is correct |
4 |
Correct |
927 ms |
19976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1272 ms |
17524 KB |
Output is correct |
2 |
Correct |
1441 ms |
16560 KB |
Output is correct |
3 |
Correct |
585 ms |
8592 KB |
Output is correct |
4 |
Correct |
1091 ms |
19536 KB |
Output is correct |