oj.uz

Submission #375009

# Submission time Handle Problem Language Result Execution time Memory
375009 2021-03-08T20:57:55 Z vot808 Two Antennas (JOI19_antennas) C++17
22 / 100
 573 ms 35188 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;
			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 502 ms 32332 KB Output is correct
2 Correct 573 ms 34952 KB Output is correct
3 Correct 373 ms 27180 KB Output is correct
4 Correct 564 ms 35036 KB Output is correct
5 Correct 213 ms 16620 KB Output is correct
6 Correct 570 ms 34972 KB Output is correct
7 Correct 478 ms 31464 KB Output is correct
8 Correct 560 ms 35188 KB Output is correct
9 Correct 55 ms 5716 KB Output is correct
10 Correct 564 ms 35136 KB Output is correct
11 Correct 310 ms 21016 KB Output is correct
12 Correct 566 ms 35000 KB Output is correct
13 Correct 307 ms 31780 KB Output is correct
14 Correct 288 ms 31060 KB Output is correct
15 Correct 269 ms 28864 KB Output is correct
16 Correct 258 ms 29676 KB Output is correct
17 Correct 314 ms 32240 KB Output is correct
18 Correct 289 ms 30324 KB Output is correct
19 Correct 283 ms 30152 KB Output is correct
20 Correct 288 ms 30244 KB Output is correct
21 Correct 274 ms 31664 KB Output is correct
22 Correct 293 ms 30964 KB Output is correct
23 Correct 285 ms 30916 KB Output is correct
24 Correct 244 ms 28560 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 -