oj.uz

Submission #203777

# Submission time Handle Problem Language Result Execution time Memory
203777 2020-02-22T06:14:11 Z dimash241 Two Antennas (JOI19_antennas) C++17
100 / 100
 951 ms 60280 KB 
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")

//# include <x86intrin.h>
# include <bits/stdc++.h>

# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
 
template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

inline void Input_Output () {
	//freopen(".in", "r", stdin);
   //freopen(".out", "w", stdout);
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 1e9 + 11;
const int mxn = 1e6 + 9;
const int N = 3e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, m, k;
struct ana {
	int h, a, b;
} a[N];
int ans[N];
int ql[N], qr[N];

struct SegTree {
	int t[N * 4];
	int mx[N * 4];
	int add[N * 4];

	inline void clear() {
		for (int i = 1; i < N * 4; ++i) {
			t[i] = -1;
			add[i] = inf;
			mx[i] = 0;
		}
	}

	inline void push (int v, int tl, int tr) {
		if (add[v] == inf) return;
		if (tl != tr) {
			add[v << 1] = min(add[v<< 1], add[v]);
			add[v << 1 | 1] = min(add[v << 1 | 1], add[v]);
		}

		t[v] = max(t[v], mx[v] - add[v]);

		add[v] = inf;
	}

	inline void recalc (int v) {
		t[v] = max(t[v<<1], t[v << 1 | 1]);
		mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
	}


	void upd (int p, int x, int v = 1, int tl = 1, int tr = n) {
		push(v, tl, tr);
		if (tl > p || p > tr) return;
		if (tl == tr) {
			mx[v] = x;
			return;
		}
		int tm = (tl + tr) >> 1;
		upd (p, x, v << 1, tl, tm);
		upd (p, x, v << 1 | 1, tm + 1, tr);

		recalc(v);

	} 

	void segDec (int l, int r, int x, int v = 1, int tl = 1, int tr = n) {
		push(v, tl,  tr);
		if (l > tr || tl > r) return;
		if (tl >= l && tr <= r) {
			add[v] = x;
			push(v, tl, tr);
			return;
		}

		int tm = (tl + tr) >> 1;
		segDec (l, r, x, v << 1, tl, tm);
		segDec (l, r, x, v << 1 | 1, tm + 1, tr);

		recalc(v);
	} 

	int get (int l, int r, int v = 1, int tl = 1, int tr = n) {
		push(v, tl, tr);
		if (tl > r || l > tr) return -1;
		if (tl >= l && tr <= r) return t[v];

		int tm = (tl + tr) >> 1;
		return max (
			get (l, r, v << 1, tl, tm)
				, get (l, r, v << 1 | 1, tm + 1, tr)
		);
	}

} T;
vector < int > st[N], en[N], q[N];

inline void solve () {
	T.clear();
	for (int i = 1; i <= n; i ++) {
		st[i].clear();
		en[i].clear();
		q[i].clear();
	}

	for (int i = 1; i <= m; i ++) {
		q[qr[i]].pb(i);
	}

	for (int i = 1; i <= n; i ++) {
		if (i + a[i].a <= n) {
			st[i + a[i].a].pb(i);
		}
		if (i + a[i].b <= n) {
			en[i + a[i].b].pb(i);
		}

		for (auto it : st[i])
			T.upd(it, a[it].h);

		if (i > a[i].a) {
			T.segDec(i - a[i].b, i - a[i].a, a[i].h);
		}

		for (auto j : q[i]) {
			ans[j] = max(ans[j], T.get(ql[j], qr[j]));
		}

		for (auto it : en[i])
			T.upd(it, 0);


	}

	
}


int main () {
   	SpeedForce;
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i].h >> a[i].a >> a[i].b;
	}
	cin >> m;
	for (int i = 1; i <= m; ++i) {
		ans[i] = -1;
		cin >> ql[i] >> qr[i];
	}

	solve();
	reverse(a + 1, a + n + 1);
	for (int i = 1; i <= m; i ++) {
		tie(ql[i], qr[i]) = mp(n - qr[i] + 1, n - ql[i] + 1);
	}
	solve();

	for (int i = 1; i <= m; i ++)
		cout << ans[i] << '\n';

   	return Accepted;
}

// B...a

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 35576 KB Output is correct
2 Correct 30 ms 35576 KB Output is correct
3 Correct 28 ms 35576 KB Output is correct
4 Correct 29 ms 35572 KB Output is correct
5 Correct 28 ms 35576 KB Output is correct
6 Correct 28 ms 35576 KB Output is correct
7 Correct 28 ms 35704 KB Output is correct
8 Correct 28 ms 35576 KB Output is correct
9 Correct 27 ms 35576 KB Output is correct
10 Correct 27 ms 35704 KB Output is correct
11 Correct 27 ms 35576 KB Output is correct
12 Correct 27 ms 35576 KB Output is correct
13 Correct 26 ms 35576 KB Output is correct
14 Correct 27 ms 35704 KB Output is correct
15 Correct 27 ms 35704 KB Output is correct
16 Correct 30 ms 35580 KB Output is correct
17 Correct 26 ms 35704 KB Output is correct
18 Correct 29 ms 35576 KB Output is correct
19 Correct 30 ms 35596 KB Output is correct
20 Correct 29 ms 35704 KB Output is correct
21 Correct 29 ms 35576 KB Output is correct
22 Correct 28 ms 35576 KB Output is correct
23 Correct 29 ms 35580 KB Output is correct
24 Correct 29 ms 35576 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 35576 KB Output is correct
2 Correct 30 ms 35576 KB Output is correct
3 Correct 28 ms 35576 KB Output is correct
4 Correct 29 ms 35572 KB Output is correct
5 Correct 28 ms 35576 KB Output is correct
6 Correct 28 ms 35576 KB Output is correct
7 Correct 28 ms 35704 KB Output is correct
8 Correct 28 ms 35576 KB Output is correct
9 Correct 27 ms 35576 KB Output is correct
10 Correct 27 ms 35704 KB Output is correct
11 Correct 27 ms 35576 KB Output is correct
12 Correct 27 ms 35576 KB Output is correct
13 Correct 26 ms 35576 KB Output is correct
14 Correct 27 ms 35704 KB Output is correct
15 Correct 27 ms 35704 KB Output is correct
16 Correct 30 ms 35580 KB Output is correct
17 Correct 26 ms 35704 KB Output is correct
18 Correct 29 ms 35576 KB Output is correct
19 Correct 30 ms 35596 KB Output is correct
20 Correct 29 ms 35704 KB Output is correct
21 Correct 29 ms 35576 KB Output is correct
22 Correct 28 ms 35576 KB Output is correct
23 Correct 29 ms 35580 KB Output is correct
24 Correct 29 ms 35576 KB Output is correct
25 Correct 124 ms 40056 KB Output is correct
26 Correct 42 ms 36344 KB Output is correct
27 Correct 174 ms 41720 KB Output is correct
28 Correct 170 ms 41592 KB Output is correct
29 Correct 123 ms 40184 KB Output is correct
30 Correct 133 ms 39928 KB Output is correct
31 Correct 133 ms 41208 KB Output is correct
32 Correct 181 ms 41592 KB Output is correct
33 Correct 168 ms 41464 KB Output is correct
34 Correct 99 ms 38648 KB Output is correct
35 Correct 165 ms 41848 KB Output is correct
36 Correct 181 ms 41592 KB Output is correct
37 Correct 106 ms 38648 KB Output is correct
38 Correct 168 ms 40568 KB Output is correct
39 Correct 50 ms 36600 KB Output is correct
40 Correct 165 ms 40624 KB Output is correct
41 Correct 144 ms 39548 KB Output is correct
42 Correct 167 ms 40568 KB Output is correct
43 Correct 79 ms 37496 KB Output is correct
44 Correct 166 ms 40568 KB Output is correct
45 Correct 54 ms 36732 KB Output is correct
46 Correct 159 ms 40568 KB Output is correct
47 Correct 63 ms 37112 KB Output is correct
48 Correct 165 ms 40568 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 43000 KB Output is correct
2 Correct 489 ms 48248 KB Output is correct
3 Correct 321 ms 44408 KB Output is correct
4 Correct 461 ms 48112 KB Output is correct
5 Correct 206 ms 41336 KB Output is correct
6 Correct 463 ms 48120 KB Output is correct
7 Correct 413 ms 46456 KB Output is correct
8 Correct 466 ms 47992 KB Output is correct
9 Correct 75 ms 37496 KB Output is correct
10 Correct 490 ms 48124 KB Output is correct
11 Correct 283 ms 43512 KB Output is correct
12 Correct 474 ms 48248 KB Output is correct
13 Correct 255 ms 45944 KB Output is correct
14 Correct 246 ms 45600 KB Output is correct
15 Correct 233 ms 45044 KB Output is correct
16 Correct 234 ms 45188 KB Output is correct
17 Correct 259 ms 46452 KB Output is correct
18 Correct 239 ms 45304 KB Output is correct
19 Correct 252 ms 45264 KB Output is correct
20 Correct 252 ms 45624 KB Output is correct
21 Correct 229 ms 45916 KB Output is correct
22 Correct 251 ms 45816 KB Output is correct
23 Correct 250 ms 45524 KB Output is correct
24 Correct 228 ms 44668 KB Output is correct

Subtask #4
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 35576 KB Output is correct
2 Correct 30 ms 35576 KB Output is correct
3 Correct 28 ms 35576 KB Output is correct
4 Correct 29 ms 35572 KB Output is correct
5 Correct 28 ms 35576 KB Output is correct
6 Correct 28 ms 35576 KB Output is correct
7 Correct 28 ms 35704 KB Output is correct
8 Correct 28 ms 35576 KB Output is correct
9 Correct 27 ms 35576 KB Output is correct
10 Correct 27 ms 35704 KB Output is correct
11 Correct 27 ms 35576 KB Output is correct
12 Correct 27 ms 35576 KB Output is correct
13 Correct 26 ms 35576 KB Output is correct
14 Correct 27 ms 35704 KB Output is correct
15 Correct 27 ms 35704 KB Output is correct
16 Correct 30 ms 35580 KB Output is correct
17 Correct 26 ms 35704 KB Output is correct
18 Correct 29 ms 35576 KB Output is correct
19 Correct 30 ms 35596 KB Output is correct
20 Correct 29 ms 35704 KB Output is correct
21 Correct 29 ms 35576 KB Output is correct
22 Correct 28 ms 35576 KB Output is correct
23 Correct 29 ms 35580 KB Output is correct
24 Correct 29 ms 35576 KB Output is correct
25 Correct 124 ms 40056 KB Output is correct
26 Correct 42 ms 36344 KB Output is correct
27 Correct 174 ms 41720 KB Output is correct
28 Correct 170 ms 41592 KB Output is correct
29 Correct 123 ms 40184 KB Output is correct
30 Correct 133 ms 39928 KB Output is correct
31 Correct 133 ms 41208 KB Output is correct
32 Correct 181 ms 41592 KB Output is correct
33 Correct 168 ms 41464 KB Output is correct
34 Correct 99 ms 38648 KB Output is correct
35 Correct 165 ms 41848 KB Output is correct
36 Correct 181 ms 41592 KB Output is correct
37 Correct 106 ms 38648 KB Output is correct
38 Correct 168 ms 40568 KB Output is correct
39 Correct 50 ms 36600 KB Output is correct
40 Correct 165 ms 40624 KB Output is correct
41 Correct 144 ms 39548 KB Output is correct
42 Correct 167 ms 40568 KB Output is correct
43 Correct 79 ms 37496 KB Output is correct
44 Correct 166 ms 40568 KB Output is correct
45 Correct 54 ms 36732 KB Output is correct
46 Correct 159 ms 40568 KB Output is correct
47 Correct 63 ms 37112 KB Output is correct
48 Correct 165 ms 40568 KB Output is correct
49 Correct 425 ms 43000 KB Output is correct
50 Correct 489 ms 48248 KB Output is correct
51 Correct 321 ms 44408 KB Output is correct
52 Correct 461 ms 48112 KB Output is correct
53 Correct 206 ms 41336 KB Output is correct
54 Correct 463 ms 48120 KB Output is correct
55 Correct 413 ms 46456 KB Output is correct
56 Correct 466 ms 47992 KB Output is correct
57 Correct 75 ms 37496 KB Output is correct
58 Correct 490 ms 48124 KB Output is correct
59 Correct 283 ms 43512 KB Output is correct
60 Correct 474 ms 48248 KB Output is correct
61 Correct 255 ms 45944 KB Output is correct
62 Correct 246 ms 45600 KB Output is correct
63 Correct 233 ms 45044 KB Output is correct
64 Correct 234 ms 45188 KB Output is correct
65 Correct 259 ms 46452 KB Output is correct
66 Correct 239 ms 45304 KB Output is correct
67 Correct 252 ms 45264 KB Output is correct
68 Correct 252 ms 45624 KB Output is correct
69 Correct 229 ms 45916 KB Output is correct
70 Correct 251 ms 45816 KB Output is correct
71 Correct 250 ms 45524 KB Output is correct
72 Correct 228 ms 44668 KB Output is correct
73 Correct 786 ms 56440 KB Output is correct
74 Correct 543 ms 49528 KB Output is correct
75 Correct 711 ms 55288 KB Output is correct
76 Correct 936 ms 60280 KB Output is correct
77 Correct 470 ms 49080 KB Output is correct
78 Correct 781 ms 57208 KB Output is correct
79 Correct 830 ms 58192 KB Output is correct
80 Correct 951 ms 60280 KB Output is correct
81 Correct 327 ms 45816 KB Output is correct
82 Correct 726 ms 55172 KB Output is correct
83 Correct 664 ms 54072 KB Output is correct
84 Correct 948 ms 60280 KB Output is correct
85 Correct 472 ms 53452 KB Output is correct
86 Correct 667 ms 56868 KB Output is correct
87 Correct 318 ms 47348 KB Output is correct
88 Correct 643 ms 56128 KB Output is correct
89 Correct 552 ms 54948 KB Output is correct
90 Correct 639 ms 56460 KB Output is correct
91 Correct 366 ms 50000 KB Output is correct
92 Correct 622 ms 56516 KB Output is correct
93 Correct 321 ms 48732 KB Output is correct
94 Correct 651 ms 56692 KB Output is correct
95 Correct 376 ms 49524 KB Output is correct
96 Correct 585 ms 55668 KB Output is correct