QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#260120#1964. Stock Price Predictionucup-team288#TL 0ms0kbC++204.3kb2023-11-21 20:24:442023-11-21 20:24:45

Judging History

你现在查看的是最新测评结果

  • [2023-11-21 20:24:45]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-11-21 20:24:44]
  • 提交

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...

output:


result: