[AtCoder] [經典競程 90 題] 010 - Score Sum Queries(★2)

題目連結:https://atcoder.jp/contests/typical90/tasks/typical90_j
題目大意:
ABC大學有 $N$ 個學生,學號 $i$ 的學生在 $C_i$ 班裡,已知第 $i$ 個學生期末考成績為 $P_i$ 。現在對於 $Q$ 筆詢問 $L_i$, $R_i$,請輸出學號在 $[L_i, R_i]$的學生的成績總和 (分班獨自統計)
算個前綴和就可以 $O(1)$ 回答了。
#include <bits/stdc++.h>
using namespace std;
using lld = int64_t;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; cin >> n;
	vector<lld> a(n), b(n);
	for (int i = 0; i < n; ++i) {
		int op, scr; cin >> op >> scr;
		if (op == 1) {
			a[i] = scr;
		} else {
			b[i] = scr;
		}
	}
	partial_sum(a.begin(), a.end(), a.begin());
	partial_sum(b.begin(), b.end(), b.begin());
	int q; cin >> q;
	while (q--) {
		int l, r; cin >> l >> r;
		--l, --r;
		if (l) cout << a[r] - a[l - 1] << ' ' << b[r] - b[l - 1] << '\n';
		else cout << a[r] << ' ' << b[r] << '\n';
	}
	return 0;
} 

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology