oj.uz

답안 #375011

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
375011 2021-03-08T21:00:36 Z vot808 Two Antennas (JOI19_antennas) C++17
22 / 100
 621 ms 39400 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.assign(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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 517 ms 35384 KB Output is correct
2 Correct 601 ms 39336 KB Output is correct
3 Correct 391 ms 27768 KB Output is correct
4 Correct 594 ms 39340 KB Output is correct
5 Correct 224 ms 18284 KB Output is correct
6 Correct 621 ms 39332 KB Output is correct
7 Correct 512 ms 34152 KB Output is correct
8 Correct 605 ms 39272 KB Output is correct
9 Correct 57 ms 6508 KB Output is correct
10 Correct 549 ms 39360 KB Output is correct
11 Correct 304 ms 24744 KB Output is correct
12 Correct 558 ms 39400 KB Output is correct
13 Correct 313 ms 38308 KB Output is correct
14 Correct 292 ms 38012 KB Output is correct
15 Correct 271 ms 37056 KB Output is correct
16 Correct 260 ms 37472 KB Output is correct
17 Correct 318 ms 38552 KB Output is correct
18 Correct 295 ms 37364 KB Output is correct
19 Correct 291 ms 37744 KB Output is correct
20 Correct 291 ms 37716 KB Output is correct
21 Correct 283 ms 38204 KB Output is correct
22 Correct 299 ms 38052 KB Output is correct
23 Correct 296 ms 38104 KB Output is correct
24 Correct 252 ms 36988 KB Output is correct

Subtask #4
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -