oj.uz

답안 #132405

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
132405 2019-07-18T19:37:57 Z Kewo Two Antennas (JOI19_antennas) C++17
22 / 100
 469 ms 79488 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mid ((x + y) / 2)
#define left (ind * 2)
#define right (ind * 2 + 1)
#define mp make_pair
#define timer ((double)clock() / CLOCKS_PER_SEC)
#define endl "\n"
#define spc " "
#define d1(x) cerr<<#x<<":"<<x<<endl
#define d2(x, y) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<endl
#define d3(x, y, z) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<endl
#define fast_io() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

typedef long long int lli;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<double, double> dd;

const int N = (int)(1e6 + 5);
const int LOG = (int)(20);
const int inf = (int)(1e9 + 5);

int n, q, h[N], a[N], b[N], ans, tree[N << 2];
vector<int> v[N];
vector<ii> pt[N];

void upd(int ind, int x, int y, int a, int val) {
	if(y < a || a < x)
		return;
	if(x == y && x == a) {
		tree[ind] = val;
		return;
	}
	upd(left, x, mid, a, val);
	upd(right, mid + 1, y, a, val);
	tree[ind] = max(tree[left], tree[right]);
}

int get(int ind, int x, int y, int a, int b) {
	if(b == 0)
		return -inf;
	if(y < a || b < x)
		return -inf;
	if(a <= x && y <= b)
		return tree[ind];
	return max(get(left, x, mid, a, b), get(right, mid + 1, y, a, b));
}

void solve() {
	memset(tree, -1, sizeof tree);
	for(int i = 1; i <= n; i++)
		pt[i].clear();
	for(int i = 1; i <= n; i++) {
		pt[min(n, i + a[i])].pb({i, 0});
		pt[min(n + 1, i + b[i] + 1)].pb({i, 1});
	}
	for(int i = 1; i <= n; i++) {
		for(auto j : pt[i]) {
			if(j.se == 0)
				upd(1, 1, n, j.fi, h[j.fi]);
			else
				upd(1, 1, n, j.fi, -1);
		}
		ans = max(ans, get(1, 1, n, max(1, i - b[i]), max(0, i - a[i])) - h[i]);
	}
}

int main() {
	fast_io();
	// freopen("inp.in", "r", stdin);
	
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> h[i] >> a[i] >> b[i];
	cin >> q;
	for(int i = 1; i <= q; i++) {
		int a, b;
		cin >> a >> b;
		// v[b].pb({a, i});
	}
	solve();
	reverse(a + 1, a + n + 1);
	reverse(b + 1, b + n + 1);
	reverse(h + 1, h + n + 1);
	solve();
	cout << ans;
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 11.0

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

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 385 ms 78084 KB Output is correct
2 Correct 469 ms 79488 KB Output is correct
3 Correct 295 ms 73316 KB Output is correct
4 Correct 421 ms 79332 KB Output is correct
5 Correct 208 ms 70512 KB Output is correct
6 Correct 431 ms 79296 KB Output is correct
7 Correct 363 ms 75644 KB Output is correct
8 Correct 422 ms 79352 KB Output is correct
9 Correct 117 ms 65396 KB Output is correct
10 Correct 415 ms 79356 KB Output is correct
11 Correct 263 ms 72492 KB Output is correct
12 Correct 417 ms 79464 KB Output is correct
13 Correct 338 ms 77152 KB Output is correct
14 Correct 315 ms 77008 KB Output is correct
15 Correct 318 ms 76544 KB Output is correct
16 Correct 321 ms 76436 KB Output is correct
17 Correct 342 ms 77524 KB Output is correct
18 Correct 325 ms 76468 KB Output is correct
19 Correct 317 ms 76784 KB Output is correct
20 Correct 315 ms 76884 KB Output is correct
21 Correct 313 ms 79188 KB Output is correct
22 Correct 307 ms 76952 KB Output is correct
23 Correct 320 ms 77024 KB Output is correct
24 Correct 295 ms 75756 KB Output is correct

Subtask #4
0 / 65.0

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