oj.uz

Submission #237182

# Submission time Handle Problem Language Result Execution time Memory
237182 2020-06-05T06:24:18 Z islingr Fire (JOI20_ho_t5) C++14
100 / 100
 605 ms 40400 KB 
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i <= (b); ++i)
#define trav(x, v) for (auto &x : v)
#define eb(x...) emplace_back(x)
#define all(x) begin(x), end(x)
#define lb(x...) lower_bound(x)

using ll = int64_t;

struct S {
	int n; vector<ll> t;
	S(int n = 0) : n{n}, t(2 * n, 0) { } 
	ll query(int r) {
		ll s = 0; int l = n;
		for (r += n; l < r; l >>= 1, r >>= 1) {
			if (l & 1) s += t[l++];
			if (r & 1) s += t[--r];
		}
		return s;
	}
	void add(int p, ll v) {
		for (t[p += n] += v; p >>= 1; )
			t[p] = t[p << 1|0] + t[p << 1|1];
	}
};

const int N = 13 << 14;
int s[N], p[N], nxt[N], t[N];
ll ans[N];
vector<int> q[N], e[N];

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m; cin >> n >> m;
	rep(i, 1, n) {
		cin >> s[i];
		p[i] = i - 1; nxt[i] = n + 1;
		while (p[i] && s[p[i]] < s[i])
			nxt[p[i]] = i, p[i] = p[p[i]];
	}
	rep(i, 1, n) if (!p[i]) p[i] = i;

	rep(i, 1, m) {
		int l, r; cin >> t[i] >> l >> r;
		q[l - 1].eb(-i); q[r].eb(i);
	}

	vector<int> a;
	rep(i, 1, n) {
		while(!a.empty() && s[a.back()] < s[i]) a.pop_back();
		a.eb(i);
		trav(j, q[i]) {
			int prev = *lb(all(a), i - t[abs(j)]);
			ll del = 1ll * s[prev] * (i - prev);
			if (j < 0) ans[-j] -= del;
			else ans[j] += del;
			e[prev].eb(j);
		}
	}

	S U(n), US(n), D(n), DS(n); ll sum = 0;
	rep(i, 1, n) {
		ll w = s[p[i]] - s[i]; sum += s[i];
		int u = i - p[i] - 1, d = nxt[i] - p[i] - 1;
		US.add(u, w * u); U.add(u, w);
		DS.add(d, w * d); D.add(d, w);
		trav(j, e[i]) {
			int t = ::t[abs(j)];
			ll del = sum;
			del += U.query(t) * t - US.query(t);
			del += DS.query(t) - D.query(t) * t;
			if (j < 0) ans[-j] -= del;
			else ans[j] += del;
		}
	}

	rep(i, 1, m) cout << ans[i] << '\n';	
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10368 KB Output is correct
2 Correct 11 ms 10368 KB Output is correct
3 Correct 11 ms 10368 KB Output is correct
4 Correct 11 ms 10496 KB Output is correct
5 Correct 10 ms 10368 KB Output is correct
6 Correct 11 ms 10368 KB Output is correct
7 Correct 10 ms 10368 KB Output is correct
8 Correct 12 ms 10496 KB Output is correct
9 Correct 10 ms 10368 KB Output is correct
10 Correct 11 ms 10368 KB Output is correct
11 Correct 12 ms 10496 KB Output is correct
12 Correct 11 ms 10496 KB Output is correct
13 Correct 11 ms 10368 KB Output is correct
14 Correct 11 ms 10368 KB Output is correct
15 Correct 11 ms 10496 KB Output is correct
16 Correct 11 ms 10496 KB Output is correct
17 Correct 10 ms 10368 KB Output is correct
18 Correct 11 ms 10368 KB Output is correct
19 Correct 12 ms 10496 KB Output is correct
20 Correct 11 ms 10368 KB Output is correct
21 Correct 11 ms 10368 KB Output is correct
22 Correct 11 ms 10368 KB Output is correct
23 Correct 11 ms 10368 KB Output is correct
24 Correct 12 ms 10460 KB Output is correct
25 Correct 11 ms 10368 KB Output is correct
26 Correct 11 ms 10368 KB Output is correct
27 Correct 10 ms 10368 KB Output is correct
28 Correct 10 ms 10496 KB Output is correct
29 Correct 10 ms 10368 KB Output is correct
30 Correct 11 ms 10368 KB Output is correct
31 Correct 11 ms 10496 KB Output is correct
32 Correct 10 ms 10496 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10368 KB Output is correct
2 Correct 305 ms 39916 KB Output is correct
3 Correct 313 ms 39272 KB Output is correct
4 Correct 318 ms 40112 KB Output is correct
5 Correct 323 ms 40236 KB Output is correct
6 Correct 305 ms 39728 KB Output is correct
7 Correct 312 ms 40308 KB Output is correct
8 Correct 327 ms 40304 KB Output is correct
9 Correct 347 ms 40220 KB Output is correct
10 Correct 288 ms 39312 KB Output is correct
11 Correct 323 ms 39944 KB Output is correct
12 Correct 298 ms 39176 KB Output is correct
13 Correct 330 ms 39788 KB Output is correct
14 Correct 298 ms 39728 KB Output is correct
15 Correct 318 ms 39988 KB Output is correct
16 Correct 317 ms 39884 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10368 KB Output is correct
2 Correct 462 ms 39020 KB Output is correct
3 Correct 445 ms 38408 KB Output is correct
4 Correct 456 ms 39760 KB Output is correct
5 Correct 462 ms 38700 KB Output is correct
6 Correct 443 ms 39148 KB Output is correct
7 Correct 457 ms 39080 KB Output is correct
8 Correct 495 ms 38940 KB Output is correct
9 Correct 495 ms 38780 KB Output is correct
10 Correct 478 ms 38668 KB Output is correct
11 Correct 493 ms 39472 KB Output is correct
12 Correct 435 ms 39020 KB Output is correct
13 Correct 480 ms 39424 KB Output is correct
14 Correct 515 ms 38896 KB Output is correct
15 Correct 460 ms 39424 KB Output is correct
16 Correct 434 ms 39148 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 39632 KB Output is correct
2 Correct 552 ms 39748 KB Output is correct
3 Correct 596 ms 40400 KB Output is correct
4 Correct 588 ms 39740 KB Output is correct
5 Correct 587 ms 39916 KB Output is correct
6 Correct 584 ms 39848 KB Output is correct
7 Correct 583 ms 40288 KB Output is correct
8 Correct 593 ms 40024 KB Output is correct
9 Correct 580 ms 39784 KB Output is correct
10 Correct 571 ms 40004 KB Output is correct
11 Correct 605 ms 40032 KB Output is correct
12 Correct 591 ms 40044 KB Output is correct
13 Correct 605 ms 39912 KB Output is correct
14 Correct 586 ms 40040 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10368 KB Output is correct
2 Correct 11 ms 10368 KB Output is correct
3 Correct 11 ms 10368 KB Output is correct
4 Correct 11 ms 10496 KB Output is correct
5 Correct 10 ms 10368 KB Output is correct
6 Correct 11 ms 10368 KB Output is correct
7 Correct 10 ms 10368 KB Output is correct
8 Correct 12 ms 10496 KB Output is correct
9 Correct 10 ms 10368 KB Output is correct
10 Correct 11 ms 10368 KB Output is correct
11 Correct 12 ms 10496 KB Output is correct
12 Correct 11 ms 10496 KB Output is correct
13 Correct 11 ms 10368 KB Output is correct
14 Correct 11 ms 10368 KB Output is correct
15 Correct 11 ms 10496 KB Output is correct
16 Correct 11 ms 10496 KB Output is correct
17 Correct 10 ms 10368 KB Output is correct
18 Correct 11 ms 10368 KB Output is correct
19 Correct 12 ms 10496 KB Output is correct
20 Correct 11 ms 10368 KB Output is correct
21 Correct 11 ms 10368 KB Output is correct
22 Correct 11 ms 10368 KB Output is correct
23 Correct 11 ms 10368 KB Output is correct
24 Correct 12 ms 10460 KB Output is correct
25 Correct 11 ms 10368 KB Output is correct
26 Correct 11 ms 10368 KB Output is correct
27 Correct 10 ms 10368 KB Output is correct
28 Correct 10 ms 10496 KB Output is correct
29 Correct 10 ms 10368 KB Output is correct
30 Correct 11 ms 10368 KB Output is correct
31 Correct 11 ms 10496 KB Output is correct
32 Correct 10 ms 10496 KB Output is correct
33 Correct 518 ms 39568 KB Output is correct
34 Correct 522 ms 40076 KB Output is correct
35 Correct 492 ms 39720 KB Output is correct
36 Correct 500 ms 39612 KB Output is correct
37 Correct 470 ms 39740 KB Output is correct
38 Correct 503 ms 40044 KB Output is correct
39 Correct 502 ms 39604 KB Output is correct
40 Correct 501 ms 39460 KB Output is correct
41 Correct 509 ms 39852 KB Output is correct
42 Correct 499 ms 39704 KB Output is correct
43 Correct 463 ms 40056 KB Output is correct
44 Correct 448 ms 40308 KB Output is correct
45 Correct 447 ms 39204 KB Output is correct
46 Correct 482 ms 39692 KB Output is correct
47 Correct 478 ms 39560 KB Output is correct
48 Correct 442 ms 39272 KB Output is correct
49 Correct 462 ms 39688 KB Output is correct
50 Correct 444 ms 40392 KB Output is correct
51 Correct 438 ms 40144 KB Output is correct
52 Correct 436 ms 39696 KB Output is correct
53 Correct 444 ms 39672 KB Output is correct
54 Correct 396 ms 39636 KB Output is correct
55 Correct 409 ms 39904 KB Output is correct
56 Correct 421 ms 40052 KB Output is correct
57 Correct 415 ms 39800 KB Output is correct
58 Correct 414 ms 39924 KB Output is correct
59 Correct 305 ms 39916 KB Output is correct
60 Correct 313 ms 39272 KB Output is correct
61 Correct 318 ms 40112 KB Output is correct
62 Correct 323 ms 40236 KB Output is correct
63 Correct 305 ms 39728 KB Output is correct
64 Correct 312 ms 40308 KB Output is correct
65 Correct 327 ms 40304 KB Output is correct
66 Correct 347 ms 40220 KB Output is correct
67 Correct 288 ms 39312 KB Output is correct
68 Correct 323 ms 39944 KB Output is correct
69 Correct 298 ms 39176 KB Output is correct
70 Correct 330 ms 39788 KB Output is correct
71 Correct 298 ms 39728 KB Output is correct
72 Correct 318 ms 39988 KB Output is correct
73 Correct 317 ms 39884 KB Output is correct
74 Correct 462 ms 39020 KB Output is correct
75 Correct 445 ms 38408 KB Output is correct
76 Correct 456 ms 39760 KB Output is correct
77 Correct 462 ms 38700 KB Output is correct
78 Correct 443 ms 39148 KB Output is correct
79 Correct 457 ms 39080 KB Output is correct
80 Correct 495 ms 38940 KB Output is correct
81 Correct 495 ms 38780 KB Output is correct
82 Correct 478 ms 38668 KB Output is correct
83 Correct 493 ms 39472 KB Output is correct
84 Correct 435 ms 39020 KB Output is correct
85 Correct 480 ms 39424 KB Output is correct
86 Correct 515 ms 38896 KB Output is correct
87 Correct 460 ms 39424 KB Output is correct
88 Correct 434 ms 39148 KB Output is correct
89 Correct 581 ms 39632 KB Output is correct
90 Correct 552 ms 39748 KB Output is correct
91 Correct 596 ms 40400 KB Output is correct
92 Correct 588 ms 39740 KB Output is correct
93 Correct 587 ms 39916 KB Output is correct
94 Correct 584 ms 39848 KB Output is correct
95 Correct 583 ms 40288 KB Output is correct
96 Correct 593 ms 40024 KB Output is correct
97 Correct 580 ms 39784 KB Output is correct
98 Correct 571 ms 40004 KB Output is correct
99 Correct 605 ms 40032 KB Output is correct
100 Correct 591 ms 40044 KB Output is correct
101 Correct 605 ms 39912 KB Output is correct
102 Correct 586 ms 40040 KB Output is correct