QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#65992 | #1964. Stock Price Prediction | dlg# | TL | 0ms | 0kb | C++17 | 3.1kb | 2022-12-05 14:07:02 | 2022-12-05 14:07:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sp ' '
#define endl '\n'
#define loop(i, l, r) for(int i=(int)(l); i<=(int)(r); i++)
#define rloop(i, l, r) for(int i=(int)(l); i>=(int)r; i--)
#define all(x) (x).begin(), (x).end()
ostream &operator<<(ostream &os, vector<int> a) {
os << "[";
for (auto it: a) os << it << sp;
os << "]";
return os;
}
const int INF = numeric_limits<int>::max() / 2;
const int N = 1e6 + 5;
struct Fenwick {
int f[N];
void update(int i, int val) {
for (; i < N; i += i & (-i)) f[i] += val;
}
int getR(int i) {
auto rec = get(i);
auto rec2 = get(i-1);
return rec+rec2;
}
private:
int get(int i) {
int ret = 0;
for (; i; i -= i & -i) ret += f[i];
return ret;
}
};
vector<int> dual(vector<int> &a, vector<int> &b, int w[], int sta, bool spec){
Fenwick fa,fb;
int lenPref = 0;
// posB must be posB - 1
auto del = [&](int posB, int lenDel) {
loop(i, 1, lenDel) fa.update(a[lenPref - i + 1], -1);
int staB = posB - lenPref + 1;
loop(i, 1, lenDel) fb.update(b[staB + i - 1], -1);
lenPref -= lenDel;
};
auto getLenJump = [&](int x){
return x-w[x];
};
vector<int> ret;
loop(i,sta,b.size()-1){
if (lenPref==a.size()-1){
del(i-1,getLenJump(lenPref));
}
while(true){
int rankA = fa.getR(a[lenPref+1]);
int rankB = fb.getR(b[i]);
if (rankA==rankB) break;
auto len = getLenJump(lenPref);
del(i-1,len);
}
fa.update(a[lenPref+1],1);
fb.update(b[i],1);
lenPref++;
if (spec) w[i] = lenPref;
if (lenPref==a.size()-1){
ret.push_back(i);
}
}
return ret;
}
struct KMPx {
int w[10005];
void init(vector<int> &s) {
w[0] = -1;
w[1] = 0;
dual(s,s,w,2,true);
}
} kmp;
//3 1 0 1
//5 2 1 1
//5 1 0 1
//5 0 -1 1
//0 1 1 2 0
void enc(vector<int> &ori) {
auto inp = ori;
sort(all(inp));
inp.erase(unique(all(inp)), inp.end());
for (auto &it: ori) it = lower_bound(all(inp), it) - inp.begin();
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
#ifdef LOCAL
freopen("1test.inp", "r", stdin);
#endif
Fenwick fa, fb;
int n, m;
cin >> n >> m;
vector<int> a = {-INF}, b = {-INF};
loop(i, 1, n) {
int t;
cin >> t;
a.push_back(t);
}
loop(i, 1, m) {
int t;
cin >> t;
b.push_back(t);
}
if (n > m) { // clearly true
cout << 0 << endl;
return 0;
}
enc(a);
enc(b);
kmp.init(a);
// loop(i,1,n) cout << kmp.w[i] << sp;
// cout << endl;
// exit(0);
// 0 1 2 3 1
vector<int> ans = dual(a,b,kmp.w,1,0);
if (ans.empty()){
cout << 0 << endl;
exit(0);
}
for(auto it:ans) cout << it-n+1 << sp;
cout << endl;
}
詳細信息
Test #1:
score: 0
Time Limit Exceeded
input:
10000 1000000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...