QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#260120 | #1964. Stock Price Prediction | ucup-team288# | TL | 0ms | 0kb | C++20 | 4.3kb | 2023-11-21 20:24:44 | 2023-11-21 20:24:45 |
answer
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i64 = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template <class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l) == r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
constexpr int P = 1e9 + 9, B = 36784;
vector<int> pw;
int mul(int a, int b) {
return 1LL * a * b % P;
}
mt19937 rng(58);
struct Info {
int sz = 1;
pair<int, int> val, first, last;
int h = 0;
Info(pair<int, int> p = {}) : val(p), first(p), last(p) {}
};
Info combine(Info a, Info b, int who) {
Info c;
c.sz = a.sz + b.sz;
c.val = who == 0 ? a.val : b.val;
c.first = a.first;
c.last = b.last;
i64 x = (b.first.second - a.last.second);
if (x < 0) { x += P; }
if (b.first.first == a.last.first) {
x = P - x;
}
c.h = (0LL + mul(a.h, pw[b.sz]) + mul(x, pw[b.sz - 1]) + b.h) % P;
return c;
}
struct Treap {
Treap *lc = nullptr, *rc = nullptr;
Info info;
Treap(pair<int, int> p = {}) : info(p) {}
};
constexpr int N = 2e6;
Treap pool[N];
Treap* newNode(pair<int, int> p) {
static int n = 0;
return &(pool[n++] = Treap(p));
}
int size(Treap *t) { return t ? t->info.sz : 0; }
void pull(Treap *t) {
t->info = Info(t->info.val);
if (t->lc) {
t->info = combine(t->lc->info, t->info, 1);
}
if (t->rc) {
t->info = combine(t->info, t->rc->info, 0);
}
}
pair<Treap*, Treap*> split(Treap *t, int s) {
if (!t) { return {t, t}; }
Treap *a, *b;
if (s <= size(t->lc)) {
b = t;
tie(a, b->lc) = split(t->lc, s);
} else {
a = t;
tie(a->rc, b) = split(t->rc, s - size(t->lc) - 1);
}
pull(t);
return {a, b};
}
Treap* merge(Treap *a, Treap *b) {
if (!a) { return b; }
if (!b) { return a; }
if (rng() % (size(a) + size(b)) <= size(a)) {
a->rc = merge(a->rc, b);
pull(a);
return a;
} else {
b->lc = merge(a, b->lc);
pull(b);
return b;
}
}
int rnk(Treap *t, pair<int, int> val) {
int res = 0;
while (t) {
if (t->info.val <= val) {
res += size(t->lc) + 1;
t = t->rc;
} else {
t = t->lc;
}
}
return res;
}
void print(Treap *t) {
#ifdef KEV
auto rec = [&](auto rec, Treap *t) -> void {
if (!t) { return; }
rec(rec, t->lc);
cerr << '(' << t->info.val.first << ", " << t->info.val.second << ") ";
rec(rec, t->rc);
};
rec(rec, t);
cerr << '\n';
#endif
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
auto solve = [&]() {
int n, m;
cin >> n >> m;
pw.resize(m);
pw[0] = 1;
for (int i = 1; i < m; i++) {
pw[i] = mul(pw[i - 1], B);
}
if (n == 1) {
cout << m << '\n';
return;
}
vector<int> a(n), b(m);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < m; i++) {
cin >> b[i];
}
i64 ha = 0;
{
Treap *t = nullptr;
for (int i = 0; i < n; i++) {
int r = rnk(t, pair(a[i], i));
auto [t1, t2] = split(t, r);
t = merge(t1, merge(newNode(pair(a[i], i)), t2));
}
ha = t->info.h;
print(t);
DE(ha);
}
Treap *t = nullptr;
for (int i = 0; i < n; i++) {
int r = rnk(t, pair(b[i], i));
auto [t1, t2] = split(t, r);
t = merge(t1, merge(newNode(pair(b[i], i)), t2));
DE(t->info.h);
}
print(t);
vector<int> ans;
if (ha == t->info.h) {
ans.push_back(0);
}
for (int i = n; i < m; i++) {
{
int r = rnk(t, pair(b[i - n], i - n));
auto [t1, t2] = split(t, r - 1);
auto [t3, t4] = split(t2, 1);
t = merge(t1, t4);
}
{
int r = rnk(t, pair(b[i], i));
auto [t1, t2] = split(t, r);
t = merge(t1, merge(newNode(pair(b[i], i)), t2));
}
if (ha == t->info.h) {
ans.push_back(i - n + 1);
}
print(t);
}
if (ans.empty()) {
cout << "0\n";
} else {
for (auto i : ans) {
cout << i + 1 << " \n"[i == ans.back()];
}
}
};
solve();
}
详细
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...