QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#34120#1964. Stock Price Predictionwater233#WA 651ms8176kbC++2.9kb2022-06-05 16:52:202022-06-05 16:52:21

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-05 16:52:21]
  • 评测
  • 测评结果:WA
  • 用时:651ms
  • 内存:8176kb
  • [2022-06-05 16:52:20]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 2e4 + 5, mod = 998244353, B = 1307;
mt19937 hua(512);
inline int add(int a, int b) {return (a += b) >= mod ? a - mod : a;}
inline int mul(int a, int b) {return 1ll * a * b % mod;}
inline int fpw(int a, int b) {
	int ans = 1;
	for(; b; b >>= 1, a = mul(a, a)) if(b & 1) ans = mul(ans, a);
	return ans;
}
int pwr[maxn], prepwr[maxn];
struct Fhq {
	int rnd[maxn], ls[maxn], rs[maxn], sz[maxn], tag[maxn];
	int val[maxn], pos[maxn], sum[maxn], rt;
	vector<int> rollback;
	int cnt;
	Fhq() {	cnt = rt = 0;}
	int newnode(int x, int k) {
		int u;
		if(rollback.size()) u = rollback.back(), rollback.pop_back();
		else u = ++ cnt;
		val[u] = x, pos[u] = k, rnd[u] = hua() % mod, ls[u] = rs[u] = 0;
		sum[u] = k, tag[u] = 0, sz[u] = 1;
		return u;
	}
	void up(int u) {
		sz[u] = sz[ls[u]] + sz[rs[u]] + 1;
		sum[u] = add(sum[ls[u]], add(mul(pwr[sz[ls[u]]], pos[u]), mul(pwr[sz[ls[u]] + 1], sum[rs[u]])));
	}
	void seta(int u, int k) {
		pos[u] -= k, tag[u] += k, sum[u] = add(sum[u], mod - mul(k, prepwr[sz[u] - 1]));
	}
	void dw(int u) {
		if(tag[u]) {
			seta(ls[u], tag[u]);
			seta(rs[u], tag[u]);
			tag[u] = 0;
		}
	}
	void split(int u, int &x, int &y, int k, int p) {
		if(!u) return x = y = 0, void();
		dw(u);
		if(val[u] < k || val[u] == k && pos[u] <= p) x = u, split(rs[u], rs[x], y, k, p);
		else y = u, split(ls[u], x, ls[y], k, p);
		up(u); 
	}
	int merge(int u, int v) {
		if(!u || !v) return u + v;
		dw(u), dw(v);
		if(rnd[u] < rnd[v]) {
			rs[u] = merge(rs[u], v), up(u);
			return u;
		}
		else {
			ls[v] = merge(u, ls[v]), up(v);
			return v;
		}
	}
	void ins(int x, int k) {
		int A, B;
		split(rt, A, B, x, k);
		rt = merge(A, merge(newnode(x, k), B));
	}
	void del(int x, int k) {
		int A, B, C;
		split(rt, A, B, x - 1, 1e9);
		split(B, B, C, x, k);
		rollback.emplace_back(B);
		rt = merge(A, C);
	}
	int qry() {
		return sum[rt];
	}
	void dfs(int u) {
		if(!u) return;
		dw(u);
		dfs(ls[u]), cout << u << ' '  << val[u] << ' ' << pos[u] << ' ' << sz[u] << ' ' << sum[u] << '\n', dfs(rs[u]);
		up(u);
	}
};
void init() {
	pwr[0] = prepwr[0] = 1;
	for(int i = 1; i < maxn; i ++) pwr[i] = mul(pwr[i - 1], B), prepwr[i] = add(prepwr[i - 1], pwr[i]);
}
int main() {
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	init();
	int n, m;
	Fhq t1, t2;
	cin >> m >> n;
	vector<int> a(m), b(n);
	for(int i = 0; i < m; i ++) cin >> a[i];
	for(int i = 0; i < n; i ++) cin >> b[i];
	for(int i = 0; i < m; i ++) {
		t1.ins(a[i], i + 1);
	}
	int ret = t1.qry();
	for(int i = 0; i < m - 1; i ++) {
		t2.ins(b[i], i + 1);
	}
	int flag = 0;
	for(int i = m - 1; i < n; i ++) {
		t2.ins(b[i], m);
		if(t2.qry() == ret) cout << i - m + 2 << ' ', flag = 1;
		t2.del(b[i - m + 1], 1);
		t2.seta(t2.rt, 1);
	}
	if(!flag) cout << 0 << '\n';
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 649ms
memory: 8176kb

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:

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 99 100 101 102 ...

result:

ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ...97 989998 989999 990000 990001 '

Test #2:

score: -100
Wrong Answer
time: 651ms
memory: 8104kb

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:

1 2 10002 20002 30002 40002 50002 60002 70002 80002 90002 100002 110002 120002 130002 140002 150002 160002 170002 180002 190002 200002 210002 220002 230002 240002 250002 260002 270002 280002 290002 300002 310002 320002 330002 340002 350002 360002 370002 380002 390002 400002 410002 420002 430002 4400...

result:

wrong answer 1st lines differ - expected: '2 10002 20002 30002 40002 5000...002 950002 960002 970002 980002', found: '1 2 10002 20002 30002 40002 50...02 950002 960002 970002 980002 '