oj.uz

Submission #375010

# Submission time Handle Problem Language Result Execution time Memory
375010 2021-03-08T20:59:45 Z vot808 Two Antennas (JOI19_antennas) C++17
22 / 100
 573 ms 39384 KB 
#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
#define endl '\n'

namespace speedy_io {
	int read_nonneg() {
		int c;
		while ((c = getchar_unlocked()) < '0' || c > '9');
		int v = c - '0';
		while ((c = getchar_unlocked()) >= '0' && c <= '9') {
			v = (v << 3) + (v << 1) + (c - '0');
		}
		return v;
	}
	
	const int max_ll_size = 20;
	void put_nonneg(ll n) {
		int i = max_ll_size;
		char output_buffer[max_ll_size];
		do {
			output_buffer[--i] = (n % 10) + '0';
			n /= 10;
		} while (n);
		do {
			putchar_unlocked(output_buffer[i]);
		} while (++i < max_ll_size);
	}
}

using namespace speedy_io;


const ll INF = 1e15;
const int MXN = 2e5;

struct Node {
	ll ans = -INF, mn = INF;
};

Node tree[4*MXN];

class SegmentTree {
	public:
		int n;
		vector<ll> lazy;
		
		void push(int &p, int &c1, int &c2) {
			lazy[c1] = max(lazy[c1], lazy[p]);
			lazy[c2] = max(lazy[c2], lazy[p]);
			tree[c1].ans = max(tree[c1].ans, lazy[c1]-tree[c1].mn);
			tree[c2].ans = max(tree[c2].ans, lazy[c2]-tree[c2].mn);
			lazy[p] = -INF;
		}
		
		void updateMin(int i, ll val, int l, int r, int p) {
			if (l > i or r < i) return;
			if (l == r) {
				lazy[p] = -INF;
				tree[p].mn = val;
				return;
			}
			
			int mid = (l + r) / 2;
			int c1 = 2*p+1, c2 = 2*p+2;
			
			if (lazy[p] != -INF) push(p, c1, c2);
			
			updateMin(i, val, l, mid, c1); updateMin(i, val, mid+1, r, c2);
			tree[p] = {max(tree[c1].ans, tree[c2].ans), min(tree[c1].mn, tree[c2].mn)};
		}
		
		void updateRangeMax(int i, int j, ll val, int l, int r, int p) {
			if (r < i or l > j) return;
			if (l >= i and r <= j) {
				lazy[p] = max(lazy[p], val);
				tree[p].ans = max(tree[p].ans, lazy[p]-tree[p].mn);
				return;
			}
			
			int mid = (l + r) / 2;
			int c1 = 2*p+1, c2 = 2*p+2;
			
			if (lazy[p] != -INF) push(p, c1, c2);
			
			updateRangeMax(i, j, val, l, mid, c1); updateRangeMax(i, j, val, mid+1, r, c2);
			tree[p] = {max(tree[c1].ans, tree[c2].ans), min(tree[c1].mn, tree[c2].mn)};
		}
		
		ll ans(int i, int j, int l, int r, int p) {
			if (l > j or r < i) return -INF;
			if (l >= i and r <= j) return tree[p].ans;
			
			int mid = (l + r) / 2;
			int c1 = 2*p+1, c2 = 2*p+2;
			
			if (lazy[p] != -INF) push(p, c1, c2);
			
			return max(ans(i, j, l, mid, c1), ans(i, j, mid+1, r, c2));
		}
	
		SegmentTree(int N) {
			n = N;
			for_(i, 0, 4*N) tree[i] = {-INF, INF};
			lazy.resize(4*n, -INF);
		}
};

int n, q; 
vector<array<int, 3>> nums; // {height, a, b}
vector<ii> qrs;
vector<ll> ans;

void solve() {
	SegmentTree tree(n);
	vector<vector<array<int, 2>>> qrLeft(n);
	
	for_(i, 0, q) qrLeft[qrs[i][1]].push_back({qrs[i][0], i});

	vector<vi> enter(n), bye(n);
	for_(i, 0, n) {
		if (i+nums[i][1] < n) enter[i+nums[i][1]].push_back(i);
		if (i+nums[i][1] < n-1) bye[min(i+nums[i][2], n-1)].push_back(i);
	}
	
	for_(i, 0, n) {
		for (auto &e: enter[i]) tree.updateMin(e, nums[e][0], 0, n-1, 0);
		
		if (i-nums[i][1] >= 0) tree.updateRangeMax(max(i-nums[i][2], 0), i-nums[i][1], nums[i][0], 0, n-1, 0);
		
		for (auto &l: qrLeft[i]) ans[l[1]] = max(ans[l[1]], tree.ans(l[0], i, 0, n-1, 0));
		
		for (auto &e: bye[i]) tree.updateMin(e, INF, 0, n-1, 0);
	}
}

int main() {
#ifdef mlocal
	freopen("test.in", "r", stdin);
#endif
	
	// ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	nums.resize(n);
	for_(i, 0, n) for_(j, 0, 3) nums[i][j] = read_nonneg();
	
	cin >> q;
	qrs.resize(q); ans.resize(q, -1);
	
	for_(i, 0, q) {
		cin >> qrs[i][0] >> qrs[i][1];
		qrs[i][0] -= 1; qrs[i][1] -= 1;
	}
	
	solve();
	reverse(nums.begin(), nums.end());
	for_(i, 0, q) {
		qrs[i][0] = n-1-qrs[i][0];
		qrs[i][1] = n-1-qrs[i][1];
		swap(qrs[i][0], qrs[i][1]);
	}
	solve();
	
	for (auto i: ans) {
		put_nonneg(i);
		cout << endl;
	}
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 35636 KB Output is correct
2 Correct 565 ms 39336 KB Output is correct
3 Correct 362 ms 27796 KB Output is correct
4 Correct 567 ms 39328 KB Output is correct
5 Correct 218 ms 18284 KB Output is correct
6 Correct 565 ms 39384 KB Output is correct
7 Correct 473 ms 34280 KB Output is correct
8 Correct 571 ms 39272 KB Output is correct
9 Correct 56 ms 6508 KB Output is correct
10 Correct 567 ms 39328 KB Output is correct
11 Correct 316 ms 24884 KB Output is correct
12 Correct 573 ms 39336 KB Output is correct
13 Correct 309 ms 38268 KB Output is correct
14 Correct 294 ms 38012 KB Output is correct
15 Correct 277 ms 37144 KB Output is correct
16 Correct 263 ms 37356 KB Output is correct
17 Correct 321 ms 38552 KB Output is correct
18 Correct 299 ms 37404 KB Output is correct
19 Correct 292 ms 37568 KB Output is correct
20 Correct 293 ms 37708 KB Output is correct
21 Correct 282 ms 38308 KB Output is correct
22 Correct 295 ms 37916 KB Output is correct
23 Correct 297 ms 38280 KB Output is correct
24 Correct 251 ms 36860 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -