| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 830855 |
2023-08-19T11:48:27 Z |
dwuy |
Matching (CEOI11_mat) |
C++14 |
|
298 ms |
65536 KB |
/// dwuy: _,\,,,_\,__,\,,_
#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK "test"
using namespace std;
typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;
const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX2 = 22;
long long MEMORY = 0;
/// IT'S TIME DOING TRIE HAHAHAHAHAAAAAAAAAAAAAAAAAAAA
struct Node{
int cnt;
Node *l, *r;
Node(){
this->cnt = 0;
this->l = this->r = NULL;
}
Node(Node *other){
this->cnt = other->cnt;
this->l = other->l;
this->r = other->r;
}
};
struct persistent_Trie{
int n;
vector<Node*> root;
persistent_Trie(int n = 0){
this->n = n;
this->root.resize(n+5);
for(int i=1; i<(int)this->root.size(); i++) this->root[i] = NULL;
this->root[0] = new Node();
}
void add(int id, int x){
assert(id<(int)this->root.size());
root[id] = new Node(root[id-1]);
Node *cur = root[id];
for(int mask = MASK(MX2); mask; mask>>=1){
if(mask&x){
if(cur->r == NULL) cur->r = new Node();
else cur->r = new Node(cur->r);
cur = cur->r;
MEMORY += sizeof(cur);
}
else{
if(cur->l == NULL) cur->l = new Node();
else cur->l = new Node(cur->l);
cur = cur->l;
MEMORY += sizeof(cur);
}
cur->cnt++;
}
}
int cntLower(int x, int id){
assert(id<(int)this->root.size());
int d = 0;
int res = 0;
int val = 0;
Node *cur = root[id];
for(int mask=MASK(MX2); mask; mask>>=1, d++){
if(val+mask<=x && cur->r!=NULL){
if(cur->l) res += cur->l->cnt;
cur = cur->r;
val += mask;
}
else if(cur->l!=NULL) cur = cur->l;
else break;
}
if(val<x && d-1==MX2) res++;
return res;
}
int order(int l, int r, int x){
return cntLower(x, r) - cntLower(x, l-1);
}
};
const int MX = 1000005; /// 1e6
int n, m;
int a[MX];
int b[MX];
int c[MX];
bool vist[MX];
void nhap(){
MEMORY += sizeof(a) + sizeof(b) + sizeof(c);
cin >> n >> m;
vector<int> tmp(m);
for(int i=1; i<=n; i++) cin >> c[i], a[c[i]] = i;
for(int i=1; i<=m; i++) cin >> b[i], tmp[i-1] = b[i];
sort(tmp.begin(), tmp.end());
for(int i=1; i<=m; i++) b[i] = lower_bound(tmp.begin(), tmp.end(), b[i]) - tmp.begin() + 1;
tmp.clear();
}
int pf[MX];
void solve(){
persistent_Trie A(n);
for(int i=1; i<=n; i++) A.add(i, a[i]);
for(int i=1; i<=n; i++) c[i] = A.order(1, i, a[i]);
pf[1] = 1;
bool f = 1;
for(int i=1, j=2; j<=n; ){
if(A.order(j-i+1, j, a[j]) == A.order(1, i, a[i])){
pf[j] = max(pf[j], i);
i++; j++;
f = !vist[j];
vist[j] = 1;
}
else if(i!=pf[i-1]) i = pf[i-1], j -= f, f = 0;
else j++;
}
vector<int> ans;
persistent_Trie B(m);
for(int i=1; i<=m; i++) B.add(i, b[i]);
for(int i=1, j=1; i<=m; ){
if(B.order(i-j+1, i, b[i]) == c[j]){
if(j==n) ans.push_back(i-n+1), j = pf[j];
else j++, i++;
}
else if(j!=pf[j-1] + 1) j = pf[j-1] + 1;
else i++;
}
cout << ans.size() << endl;
for(int &x: ans) cout << x << ' ';
// cerr << setprecision(3) << fixed << 1.0*MEMORY/1000000.0 << "mb";
}
int32_t main(){
fastIO;
// file(TASK);
nhap();
solve();
return 0;
}
/**
6 12
2 5 3 4 1 6
10 45 25 30 5 47 31 35 4 50 33 20
6 15
1 4 2 5 3 6
2 8 4 9 6 10 7 11 12 23 26 24 27 25 28
--------------------------------------
3
1 3 10
3 4
1 3 2
1 3 5 4
--------
4 8
1 3 2 4
1 5 2 6 8 7 9 10
-----------------
2
1 4
5 7
5 4 2 3 1
2 4 9 6 3 5 1
-----------------
1
3
4 10
1 2 3 4
1 3 5 7 6 2 4 8 9 10
--------------------
3
1 6 7
4 10
4 3 2 1
1 3 5 7 6 4 8 2 9 10
--------------------
0
5 1 1
1 1 2
7 1 3
8 1 4
2 2 5
10 3 6
3 1 7
12 1 8
13 1 9
4 2 10
15 3 11
16 4 12
6 5 13
17 6 14
9 7 15
18 8 16
19 9 17
11 10 18
20 11 19
14 1 20
21 1 21
22 1 22
**/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
18304 KB |
Output is correct |
| 2 |
Correct |
23 ms |
17348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
19488 KB |
Output is correct |
| 2 |
Correct |
25 ms |
18644 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
112 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
112 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
107 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
296 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
275 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
298 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
241 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
