oj.uz

Submission #455251

# Submission time Handle Problem Language Result Execution time Memory
455251 2021-08-05T17:59:14 Z valerikk Fire (JOI20_ho_t5) C++17
100 / 100
 485 ms 115968 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <random>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef long double ld;

const int INF = 1e9;
const int N = 400010;

struct Fenwick {
	int n;
	vector<ll> f;

	void upd(int ind, int d) {
		for (int i = ind + 1; i <= n; i += i & -i) {
			f[i] += d;
		}
	}

	ll get(int r) {
		ll sum = 0;
		for (int i = r; i > 0; i -= i & -i) {
			sum += f[i];
		}
		return sum;
	}

	ll get(int l, int r) {
		if (l >= r) {
			return 0;
		}
		return get(r) - get(l);
	}

	Fenwick(int n_ = 0) : n(n_) {
		f.assign(n + 1, 0ll);
	}
};

int n, q;
int s[N];
int t[N], L[N], R[N];
vector<int> by_t[N];
ll ans[N];
pair<int, int> mx[2 * N];
vector<pair<int, int>> updl[N], updr[N];
Fenwick fl, fr;

void add(int l, int r, int ind, int d, int type) {
	if (type == 0) {
		updl[l].push_back({ind, d});
		updl[r + 1].push_back({ind, -d});
	} else {
		updr[l].push_back({ind, d});
		updr[r + 1].push_back({ind, -d});
	}
}

pair<int, int> get_max(int l, int r) {
	l += n, r += n;
	pair<int, int> res = {-INF, -INF};
	while (l < r) {
		if (l & 1) {
			res = max(res, mx[l]);
			++l;
		}
		if (r & 1) {
			--r;
			res = max(res, mx[r]);
		}
		l >>= 1, r >>= 1;
	}
	return res;
}

void rec(int l, int r) {
	if (l > r) {
		return;
	}
	int m = get_max(l, r + 1).second;
	rec(l, m - 1);
	rec(m + 1, r);
	if (m - l < r - m) {
		for (int i = l; i <= m; ++i) {
			add(m - i + 1, r - i + 1, i, s[m], 0);
		}
	} else {
		for (int i = m; i <= r; ++i) {
			add(i - m + 1, i - l + 1, i, s[m], 1);
		}
	}
} 

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> q;
	for (int i = 0; i < n; ++i) {
		cin >> s[i];
	}
	for (int i = 0; i < n; ++i) {
		s[i + n] = s[i];
		s[i] = -INF;
	}
	for (int i = 0; i < q; ++i) {
		cin >> t[i] >> L[i] >> R[i];
		--L[i];
		++t[i];
		L[i] += n, R[i] += n;
		by_t[t[i]].push_back(i);
	}
	n *= 2;
	for (int i = 0; i < n; ++i) {
		mx[i + n] = {s[i], i};
	}
	for (int i = n - 1; i > 0; --i) {
		mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
	}
	rec(0, n - 1);
	fl = fr = Fenwick(n);
	for (int t = 1; t <= n; ++t) {
		for (auto [ind, d] : updl[t]) {
			fl.upd(ind, d);
		}
		for (auto [ind, d] : updr[t]) {
			fr.upd(ind, d);
		}
		for (int i : by_t[t]) {
			ans[i] += fr.get(L[i], R[i]);
			ans[i] += fl.get(L[i] - t + 1, R[i] - t + 1);
		}
	}
	for (int i = 0; i < q; ++i) {
		cout << ans[i] << "\n";
	}
	return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28492 KB Output is correct
2 Correct 18 ms 28548 KB Output is correct
3 Correct 18 ms 28496 KB Output is correct
4 Correct 20 ms 28496 KB Output is correct
5 Correct 18 ms 28492 KB Output is correct
6 Correct 18 ms 28608 KB Output is correct
7 Correct 17 ms 28492 KB Output is correct
8 Correct 18 ms 28536 KB Output is correct
9 Correct 20 ms 28596 KB Output is correct
10 Correct 20 ms 28588 KB Output is correct
11 Correct 19 ms 28492 KB Output is correct
12 Correct 19 ms 28492 KB Output is correct
13 Correct 18 ms 28496 KB Output is correct
14 Correct 18 ms 28492 KB Output is correct
15 Correct 18 ms 28536 KB Output is correct
16 Correct 20 ms 28592 KB Output is correct
17 Correct 17 ms 28532 KB Output is correct
18 Correct 20 ms 28504 KB Output is correct
19 Correct 19 ms 28608 KB Output is correct
20 Correct 18 ms 28512 KB Output is correct
21 Correct 19 ms 28604 KB Output is correct
22 Correct 19 ms 28492 KB Output is correct
23 Correct 18 ms 28516 KB Output is correct
24 Correct 18 ms 28608 KB Output is correct
25 Correct 19 ms 28492 KB Output is correct
26 Correct 18 ms 28576 KB Output is correct
27 Correct 18 ms 28492 KB Output is correct
28 Correct 18 ms 28540 KB Output is correct
29 Correct 18 ms 28492 KB Output is correct
30 Correct 18 ms 28604 KB Output is correct
31 Correct 18 ms 28568 KB Output is correct
32 Correct 18 ms 28492 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28492 KB Output is correct
2 Correct 354 ms 108200 KB Output is correct
3 Correct 367 ms 109840 KB Output is correct
4 Correct 368 ms 108736 KB Output is correct
5 Correct 375 ms 111456 KB Output is correct
6 Correct 385 ms 109684 KB Output is correct
7 Correct 376 ms 109500 KB Output is correct
8 Correct 402 ms 111052 KB Output is correct
9 Correct 382 ms 110488 KB Output is correct
10 Correct 359 ms 107788 KB Output is correct
11 Correct 368 ms 110060 KB Output is correct
12 Correct 365 ms 108840 KB Output is correct
13 Correct 365 ms 109296 KB Output is correct
14 Correct 376 ms 110364 KB Output is correct
15 Correct 393 ms 110128 KB Output is correct
16 Correct 403 ms 110944 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28492 KB Output is correct
2 Correct 453 ms 112908 KB Output is correct
3 Correct 418 ms 111224 KB Output is correct
4 Correct 467 ms 115968 KB Output is correct
5 Correct 427 ms 110336 KB Output is correct
6 Correct 436 ms 111728 KB Output is correct
7 Correct 428 ms 111884 KB Output is correct
8 Correct 458 ms 110928 KB Output is correct
9 Correct 446 ms 110416 KB Output is correct
10 Correct 454 ms 110620 KB Output is correct
11 Correct 465 ms 114652 KB Output is correct
12 Correct 449 ms 113604 KB Output is correct
13 Correct 460 ms 113764 KB Output is correct
14 Correct 452 ms 109140 KB Output is correct
15 Correct 462 ms 113292 KB Output is correct
16 Correct 478 ms 112116 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 99204 KB Output is correct
2 Correct 327 ms 99556 KB Output is correct
3 Correct 323 ms 101244 KB Output is correct
4 Correct 318 ms 98720 KB Output is correct
5 Correct 316 ms 99096 KB Output is correct
6 Correct 335 ms 99932 KB Output is correct
7 Correct 331 ms 101076 KB Output is correct
8 Correct 318 ms 100340 KB Output is correct
9 Correct 322 ms 99168 KB Output is correct
10 Correct 320 ms 100480 KB Output is correct
11 Correct 319 ms 99532 KB Output is correct
12 Correct 334 ms 99888 KB Output is correct
13 Correct 326 ms 99580 KB Output is correct
14 Correct 321 ms 99608 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28492 KB Output is correct
2 Correct 18 ms 28548 KB Output is correct
3 Correct 18 ms 28496 KB Output is correct
4 Correct 20 ms 28496 KB Output is correct
5 Correct 18 ms 28492 KB Output is correct
6 Correct 18 ms 28608 KB Output is correct
7 Correct 17 ms 28492 KB Output is correct
8 Correct 18 ms 28536 KB Output is correct
9 Correct 20 ms 28596 KB Output is correct
10 Correct 20 ms 28588 KB Output is correct
11 Correct 19 ms 28492 KB Output is correct
12 Correct 19 ms 28492 KB Output is correct
13 Correct 18 ms 28496 KB Output is correct
14 Correct 18 ms 28492 KB Output is correct
15 Correct 18 ms 28536 KB Output is correct
16 Correct 20 ms 28592 KB Output is correct
17 Correct 17 ms 28532 KB Output is correct
18 Correct 20 ms 28504 KB Output is correct
19 Correct 19 ms 28608 KB Output is correct
20 Correct 18 ms 28512 KB Output is correct
21 Correct 19 ms 28604 KB Output is correct
22 Correct 19 ms 28492 KB Output is correct
23 Correct 18 ms 28516 KB Output is correct
24 Correct 18 ms 28608 KB Output is correct
25 Correct 19 ms 28492 KB Output is correct
26 Correct 18 ms 28576 KB Output is correct
27 Correct 18 ms 28492 KB Output is correct
28 Correct 18 ms 28540 KB Output is correct
29 Correct 18 ms 28492 KB Output is correct
30 Correct 18 ms 28604 KB Output is correct
31 Correct 18 ms 28568 KB Output is correct
32 Correct 18 ms 28492 KB Output is correct
33 Correct 354 ms 108200 KB Output is correct
34 Correct 367 ms 109840 KB Output is correct
35 Correct 368 ms 108736 KB Output is correct
36 Correct 375 ms 111456 KB Output is correct
37 Correct 385 ms 109684 KB Output is correct
38 Correct 376 ms 109500 KB Output is correct
39 Correct 402 ms 111052 KB Output is correct
40 Correct 382 ms 110488 KB Output is correct
41 Correct 359 ms 107788 KB Output is correct
42 Correct 368 ms 110060 KB Output is correct
43 Correct 365 ms 108840 KB Output is correct
44 Correct 365 ms 109296 KB Output is correct
45 Correct 376 ms 110364 KB Output is correct
46 Correct 393 ms 110128 KB Output is correct
47 Correct 403 ms 110944 KB Output is correct
48 Correct 453 ms 112908 KB Output is correct
49 Correct 418 ms 111224 KB Output is correct
50 Correct 467 ms 115968 KB Output is correct
51 Correct 427 ms 110336 KB Output is correct
52 Correct 436 ms 111728 KB Output is correct
53 Correct 428 ms 111884 KB Output is correct
54 Correct 458 ms 110928 KB Output is correct
55 Correct 446 ms 110416 KB Output is correct
56 Correct 454 ms 110620 KB Output is correct
57 Correct 465 ms 114652 KB Output is correct
58 Correct 449 ms 113604 KB Output is correct
59 Correct 460 ms 113764 KB Output is correct
60 Correct 452 ms 109140 KB Output is correct
61 Correct 462 ms 113292 KB Output is correct
62 Correct 478 ms 112116 KB Output is correct
63 Correct 318 ms 99204 KB Output is correct
64 Correct 327 ms 99556 KB Output is correct
65 Correct 323 ms 101244 KB Output is correct
66 Correct 318 ms 98720 KB Output is correct
67 Correct 316 ms 99096 KB Output is correct
68 Correct 335 ms 99932 KB Output is correct
69 Correct 331 ms 101076 KB Output is correct
70 Correct 318 ms 100340 KB Output is correct
71 Correct 322 ms 99168 KB Output is correct
72 Correct 320 ms 100480 KB Output is correct
73 Correct 319 ms 99532 KB Output is correct
74 Correct 334 ms 99888 KB Output is correct
75 Correct 326 ms 99580 KB Output is correct
76 Correct 321 ms 99608 KB Output is correct
77 Correct 451 ms 111972 KB Output is correct
78 Correct 485 ms 114240 KB Output is correct
79 Correct 481 ms 114224 KB Output is correct
80 Correct 435 ms 112208 KB Output is correct
81 Correct 457 ms 111768 KB Output is correct
82 Correct 456 ms 113164 KB Output is correct
83 Correct 477 ms 112040 KB Output is correct
84 Correct 464 ms 109956 KB Output is correct
85 Correct 462 ms 112892 KB Output is correct
86 Correct 456 ms 114632 KB Output is correct
87 Correct 405 ms 111424 KB Output is correct
88 Correct 391 ms 109624 KB Output is correct
89 Correct 377 ms 107080 KB Output is correct
90 Correct 416 ms 110636 KB Output is correct
91 Correct 413 ms 109844 KB Output is correct
92 Correct 395 ms 110304 KB Output is correct
93 Correct 400 ms 110852 KB Output is correct
94 Correct 400 ms 111408 KB Output is correct
95 Correct 398 ms 111568 KB Output is correct
96 Correct 398 ms 111876 KB Output is correct
97 Correct 398 ms 110116 KB Output is correct
98 Correct 402 ms 108960 KB Output is correct
99 Correct 397 ms 111272 KB Output is correct
100 Correct 422 ms 111260 KB Output is correct
101 Correct 382 ms 108920 KB Output is correct
102 Correct 413 ms 110312 KB Output is correct