oj.uz

Submission #430494

# Submission time Handle Problem Language Result Execution time Memory
430494 2021-06-16T14:40:51 Z Return_0 Two Antennas (JOI19_antennas) C++17
100 / 100
 773 ms 54648 KB 
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef int ll;
typedef long double ld;
typedef pair <ll, ll> pll;

#ifdef SINA
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << std::endl; }
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); }
#define dbg2(x, j, n) cout<< #x << " : "; output((j), (n), x, 1); cout.flush();
#else
#define dbg(...) 0
#define dbg2(x, j, n) 0
#endif
#define SZ(x) ((ll)((x).size()))
#define File(s, t) freopen(s ".txt", "r", stdin); freopen(t ".txt", "w", stdout);
#define input(j, n, a) for (int _i = (j); _i < (n)+(j); _i++) cin>> a[_i];
#define output(j, n, a, t) for (int _i = (j); _i < (n)+(j); _i++) cout<< a[_i] << (((t) && _i != (n)+(j)-1)? ' ' : '\n');
#define kill(x) return cout<< (x) << endl, 0
#define cl const ll
#define fr first
#define sc second
#define lc (v << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
#define All(x) (x).begin(), (x).end()

cl inf = sizeof(ll) == 4 ? (1e9 + 10) : (3e18), mod = 1e9 + 7, MOD = 998244353;

template <class A,class B> ostream& operator << (ostream& out,const pair<A,B>&a){return out<<'('<<a.first<<", "<<a.second<<')';}
template <class A> ostream& operator << (ostream& out, const vector<A> &a) {
	out<< '['; for (int i = -1; ++i < int(a.size());) out<< a[i] << (i + 1 < int(a.size()) ? ", " : ""); return out<<']'; }
template <class T, typename _t = less <T> > using Tree = tree <T, null_type, _t, rb_tree_tag, tree_order_statistics_node_update>;

cl N = 2e5 + 7;

struct segtree {
	ll l, r, mx, mn, Cmx, Cmn, ans;
	segtree *lt, *rt;
	inline segtree (cl &L = 1, cl &R = N - 2) : l(L), r(R), mx(-inf), Cmx(-inf), mn(inf), Cmn(inf), ans(-1) {}

	void build () {
		if (l == r) return;
		lt = new segtree (l, mid);
		rt = new segtree (mid + 1, r);
		lt->build();
		rt->build();
	}

	inline void push (cl &M, cl &m) { Cmn = min(Cmn, m); Cmx = max(Cmx, M); ans = max({ans, mx - Cmn, Cmx - mn}); }
	inline void shift () { lt->push(Cmx, Cmn); rt->push(Cmx, Cmn); Cmx = -inf; Cmn = inf; }

	void toggle (cl &pos, cl &x) {
		if (l == r) {
			Cmx = -inf, Cmn = inf;
			if (mn != x) mn = mx = x;
			else mn = inf, mx = -inf;
			return;
		}
		shift();
		if (pos <= lt->r) lt->toggle(pos, x);
		else rt->toggle(pos, x);
		mx = max(lt->mx, rt->mx); mn = min(lt->mn, rt->mn); ans = max(lt->ans, rt->ans);
	}

	void upd (cl &ql, cl &qr, cl &x) {
		if (r < ql || qr < l) return;
		if (ql <= l && r <= qr) {
			push(x, x);
			return;
		}
		shift();
		lt->upd(ql, qr, x);
		rt->upd(ql, qr, x);
		ans = max(lt->ans, rt->ans);
	}

	ll ask (cl &ql, cl &qr) {
		if (r < ql || qr < l) return -1;
		if (ql <= l && r <= qr) return ans;
		shift();
		return max(lt->ask(ql, qr), rt->ask(ql, qr));
	}
} seg;

ll h [N], A [N], B [N], ans [N], n, q;
vector <pll> query [N];
vector <ll> vec [N];

int main ()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin>> n;
	for (ll i = 1; i <= n; i++) {
		cin>> h[i] >> A[i] >> B[i];
		vec[min(n + 1, i + A[i])].push_back(i); vec[min(n + 1, i + B[i] + 1)].push_back(i);
	}

	cin>> q;
	for (ll i = 1, l, r; i <= q; i++) {
		cin>> l >> r;
		query[r].push_back({l, i});
	}
	
	seg.r = n; seg.build();
	for (ll i = 1; i <= n; i++) {
		for (auto &x : vec[i]) seg.toggle(x, h[x]);
		seg.upd(i - B[i], i - A[i], h[i]);
		for (auto [l, id] : query[i]) ans[id] = max(-1, seg.ask(l, i));
	}
	
	output(1, q, ans, 0);

	cerr<< "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";

	return 0;
}
/*
5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
5
1 2
2 3
1 3
1 4
1 5

20
260055884 2 15
737689751 5 5
575359903 1 15
341907415 14 14
162026576 9 19
55126745 10 19
95712405 11 14
416027186 8 13
370819848 11 14
629309664 4 13
822713895 5 15
390716905 13 17
577166133 8 19
195931195 10 17
377030463 14 17
968486685 11 19
963040581 4 10
566835557 1 12
586336111 6 16
385865831 8 9
1
1 20

*/

Compilation message

antennas.cpp: In constructor 'segtree::segtree(const ll&, const ll&)':
antennas.cpp:49:19: warning: 'segtree::Cmx' will be initialized after [-Wreorder]
   49 |  ll l, r, mx, mn, Cmx, Cmn, ans;
      |                   ^~~
antennas.cpp:49:15: warning:   'll segtree::mn' [-Wreorder]
   49 |  ll l, r, mx, mn, Cmx, Cmn, ans;
      |               ^~
antennas.cpp:51:9: warning:   when initialized here [-Wreorder]
   51 |  inline segtree (cl &L = 1, cl &R = N - 2) : l(L), r(R), mx(-inf), Cmx(-inf), mn(inf), Cmn(inf), ans(-1) {}
      |         ^~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 10 ms 9676 KB Output is correct
3 Correct 9 ms 9724 KB Output is correct
4 Correct 8 ms 9784 KB Output is correct
5 Correct 9 ms 9728 KB Output is correct
6 Correct 9 ms 9676 KB Output is correct
7 Correct 9 ms 9804 KB Output is correct
8 Correct 8 ms 9804 KB Output is correct
9 Correct 8 ms 9676 KB Output is correct
10 Correct 8 ms 9724 KB Output is correct
11 Correct 8 ms 9720 KB Output is correct
12 Correct 10 ms 9692 KB Output is correct
13 Correct 8 ms 9724 KB Output is correct
14 Correct 10 ms 9744 KB Output is correct
15 Correct 8 ms 9676 KB Output is correct
16 Correct 9 ms 9804 KB Output is correct
17 Correct 8 ms 9676 KB Output is correct
18 Correct 8 ms 9676 KB Output is correct
19 Correct 8 ms 9676 KB Output is correct
20 Correct 10 ms 9676 KB Output is correct
21 Correct 10 ms 9700 KB Output is correct
22 Correct 8 ms 9744 KB Output is correct
23 Correct 8 ms 9676 KB Output is correct
24 Correct 9 ms 9756 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 10 ms 9676 KB Output is correct
3 Correct 9 ms 9724 KB Output is correct
4 Correct 8 ms 9784 KB Output is correct
5 Correct 9 ms 9728 KB Output is correct
6 Correct 9 ms 9676 KB Output is correct
7 Correct 9 ms 9804 KB Output is correct
8 Correct 8 ms 9804 KB Output is correct
9 Correct 8 ms 9676 KB Output is correct
10 Correct 8 ms 9724 KB Output is correct
11 Correct 8 ms 9720 KB Output is correct
12 Correct 10 ms 9692 KB Output is correct
13 Correct 8 ms 9724 KB Output is correct
14 Correct 10 ms 9744 KB Output is correct
15 Correct 8 ms 9676 KB Output is correct
16 Correct 9 ms 9804 KB Output is correct
17 Correct 8 ms 9676 KB Output is correct
18 Correct 8 ms 9676 KB Output is correct
19 Correct 8 ms 9676 KB Output is correct
20 Correct 10 ms 9676 KB Output is correct
21 Correct 10 ms 9700 KB Output is correct
22 Correct 8 ms 9744 KB Output is correct
23 Correct 8 ms 9676 KB Output is correct
24 Correct 9 ms 9756 KB Output is correct
25 Correct 101 ms 14500 KB Output is correct
26 Correct 20 ms 10608 KB Output is correct
27 Correct 124 ms 16544 KB Output is correct
28 Correct 153 ms 16668 KB Output is correct
29 Correct 113 ms 14484 KB Output is correct
30 Correct 101 ms 14484 KB Output is correct
31 Correct 105 ms 15740 KB Output is correct
32 Correct 124 ms 16644 KB Output is correct
33 Correct 146 ms 16068 KB Output is correct
34 Correct 74 ms 13204 KB Output is correct
35 Correct 120 ms 16460 KB Output is correct
36 Correct 136 ms 16724 KB Output is correct
37 Correct 79 ms 13204 KB Output is correct
38 Correct 133 ms 15700 KB Output is correct
39 Correct 25 ms 10788 KB Output is correct
40 Correct 153 ms 15812 KB Output is correct
41 Correct 99 ms 14072 KB Output is correct
42 Correct 127 ms 15664 KB Output is correct
43 Correct 47 ms 11852 KB Output is correct
44 Correct 121 ms 15684 KB Output is correct
45 Correct 29 ms 10920 KB Output is correct
46 Correct 136 ms 15720 KB Output is correct
47 Correct 38 ms 11468 KB Output is correct
48 Correct 145 ms 15716 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 41844 KB Output is correct
2 Correct 414 ms 45508 KB Output is correct
3 Correct 255 ms 34844 KB Output is correct
4 Correct 393 ms 45552 KB Output is correct
5 Correct 147 ms 26152 KB Output is correct
6 Correct 393 ms 45548 KB Output is correct
7 Correct 371 ms 40884 KB Output is correct
8 Correct 411 ms 45544 KB Output is correct
9 Correct 52 ms 15300 KB Output is correct
10 Correct 391 ms 45620 KB Output is correct
11 Correct 212 ms 32096 KB Output is correct
12 Correct 395 ms 45452 KB Output is correct
13 Correct 205 ms 43376 KB Output is correct
14 Correct 199 ms 43420 KB Output is correct
15 Correct 185 ms 43448 KB Output is correct
16 Correct 183 ms 43700 KB Output is correct
17 Correct 201 ms 43540 KB Output is correct
18 Correct 200 ms 43760 KB Output is correct
19 Correct 197 ms 43296 KB Output is correct
20 Correct 232 ms 43356 KB Output is correct
21 Correct 188 ms 43352 KB Output is correct
22 Correct 193 ms 43432 KB Output is correct
23 Correct 209 ms 43384 KB Output is correct
24 Correct 205 ms 43440 KB Output is correct

Subtask #4
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 10 ms 9676 KB Output is correct
3 Correct 9 ms 9724 KB Output is correct
4 Correct 8 ms 9784 KB Output is correct
5 Correct 9 ms 9728 KB Output is correct
6 Correct 9 ms 9676 KB Output is correct
7 Correct 9 ms 9804 KB Output is correct
8 Correct 8 ms 9804 KB Output is correct
9 Correct 8 ms 9676 KB Output is correct
10 Correct 8 ms 9724 KB Output is correct
11 Correct 8 ms 9720 KB Output is correct
12 Correct 10 ms 9692 KB Output is correct
13 Correct 8 ms 9724 KB Output is correct
14 Correct 10 ms 9744 KB Output is correct
15 Correct 8 ms 9676 KB Output is correct
16 Correct 9 ms 9804 KB Output is correct
17 Correct 8 ms 9676 KB Output is correct
18 Correct 8 ms 9676 KB Output is correct
19 Correct 8 ms 9676 KB Output is correct
20 Correct 10 ms 9676 KB Output is correct
21 Correct 10 ms 9700 KB Output is correct
22 Correct 8 ms 9744 KB Output is correct
23 Correct 8 ms 9676 KB Output is correct
24 Correct 9 ms 9756 KB Output is correct
25 Correct 101 ms 14500 KB Output is correct
26 Correct 20 ms 10608 KB Output is correct
27 Correct 124 ms 16544 KB Output is correct
28 Correct 153 ms 16668 KB Output is correct
29 Correct 113 ms 14484 KB Output is correct
30 Correct 101 ms 14484 KB Output is correct
31 Correct 105 ms 15740 KB Output is correct
32 Correct 124 ms 16644 KB Output is correct
33 Correct 146 ms 16068 KB Output is correct
34 Correct 74 ms 13204 KB Output is correct
35 Correct 120 ms 16460 KB Output is correct
36 Correct 136 ms 16724 KB Output is correct
37 Correct 79 ms 13204 KB Output is correct
38 Correct 133 ms 15700 KB Output is correct
39 Correct 25 ms 10788 KB Output is correct
40 Correct 153 ms 15812 KB Output is correct
41 Correct 99 ms 14072 KB Output is correct
42 Correct 127 ms 15664 KB Output is correct
43 Correct 47 ms 11852 KB Output is correct
44 Correct 121 ms 15684 KB Output is correct
45 Correct 29 ms 10920 KB Output is correct
46 Correct 136 ms 15720 KB Output is correct
47 Correct 38 ms 11468 KB Output is correct
48 Correct 145 ms 15716 KB Output is correct
49 Correct 326 ms 41844 KB Output is correct
50 Correct 414 ms 45508 KB Output is correct
51 Correct 255 ms 34844 KB Output is correct
52 Correct 393 ms 45552 KB Output is correct
53 Correct 147 ms 26152 KB Output is correct
54 Correct 393 ms 45548 KB Output is correct
55 Correct 371 ms 40884 KB Output is correct
56 Correct 411 ms 45544 KB Output is correct
57 Correct 52 ms 15300 KB Output is correct
58 Correct 391 ms 45620 KB Output is correct
59 Correct 212 ms 32096 KB Output is correct
60 Correct 395 ms 45452 KB Output is correct
61 Correct 205 ms 43376 KB Output is correct
62 Correct 199 ms 43420 KB Output is correct
63 Correct 185 ms 43448 KB Output is correct
64 Correct 183 ms 43700 KB Output is correct
65 Correct 201 ms 43540 KB Output is correct
66 Correct 200 ms 43760 KB Output is correct
67 Correct 197 ms 43296 KB Output is correct
68 Correct 232 ms 43356 KB Output is correct
69 Correct 188 ms 43352 KB Output is correct
70 Correct 193 ms 43432 KB Output is correct
71 Correct 209 ms 43384 KB Output is correct
72 Correct 205 ms 43440 KB Output is correct
73 Correct 542 ms 48728 KB Output is correct
74 Correct 446 ms 46372 KB Output is correct
75 Correct 596 ms 43464 KB Output is correct
76 Correct 773 ms 54588 KB Output is correct
77 Correct 311 ms 32312 KB Output is correct
78 Correct 637 ms 51816 KB Output is correct
79 Correct 650 ms 49712 KB Output is correct
80 Correct 657 ms 54588 KB Output is correct
81 Correct 231 ms 22720 KB Output is correct
82 Correct 503 ms 50204 KB Output is correct
83 Correct 545 ms 40592 KB Output is correct
84 Correct 642 ms 54648 KB Output is correct
85 Correct 383 ms 48160 KB Output is correct
86 Correct 539 ms 51328 KB Output is correct
87 Correct 235 ms 44772 KB Output is correct
88 Correct 547 ms 51692 KB Output is correct
89 Correct 523 ms 49480 KB Output is correct
90 Correct 574 ms 51800 KB Output is correct
91 Correct 341 ms 46256 KB Output is correct
92 Correct 566 ms 51152 KB Output is correct
93 Correct 277 ms 44840 KB Output is correct
94 Correct 550 ms 51412 KB Output is correct
95 Correct 301 ms 45660 KB Output is correct
96 Correct 533 ms 51332 KB Output is correct