oj.uz

답안 #670520

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
670520 2022-12-09T12:28:46 Z ymm Two Antennas (JOI19_antennas) C++17
0 / 100
 225 ms 35100 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200'010;
const int inf = 1e9 + 10;

struct {
	int mnr, mxr;
	int mni, mxi;
	int mxv;
} seg[N*4];

void init(int i, int b, int e)
{
	seg[i] = {inf, -inf, inf, -inf, -inf};
	if (e-b == 1)
		return;
	init(2*i+1, b, (b+e)/2);
	init(2*i+2, (b+e)/2, e);
}

void insertr_node(int mn, int mx, int i)
{
	seg[i].mnr = min(seg[i].mnr, mn);
	seg[i].mxr = max(seg[i].mxr, mx);
	seg[i].mxv = max({seg[i].mxv, mx - seg[i].mni, seg[i].mxi - mn});
}

void ppg(int i)
{
	insertr_node(seg[i].mnr, seg[i].mxr, 2*i+1);
	insertr_node(seg[i].mnr, seg[i].mxr, 2*i+2);
}

void up(int i)
{
	seg[i].mni = min(seg[2*i+1].mni, seg[2*i+2].mni);
	seg[i].mxi = max(seg[2*i+1].mxi, seg[2*i+2].mxi);
	seg[i].mxv = max(seg[2*i+1].mxv, seg[2*i+2].mxv);
}

void insertr(int l, int r, int x, int i, int b, int e)
{
	if (l <= b && e <= r) {
		insertr_node(x, x, i);
		return;
	}
	if (r <= b || e <= l)
		return;
	ppg(i);
	insertr(l, r, x, 2*i+1, b, (b+e)/2);
	insertr(l, r, x, 2*i+2, (b+e)/2, e);
	up(i);
}

void changei(int p, int x, int i, int b, int e)
{
	if (e-b == 1) {
		seg[i].mni = x == -1? inf: x;
		seg[i].mxi = x == -1? -inf: x;
		return;
	}
	ppg(i);
	if (p < (b+e)/2)
		changei(p, x, 2*i+1, b, (b+e)/2);
	else
		changei(p, x, 2*i+2, (b+e)/2, e);
	up(i);
}

int get(int l, int r, int i, int b, int e)
{
	if (l <= b && e <= r)
		return seg[i].mxv;
	if (r <= b || e <= l)
		return -inf;
	ppg(i);
	return max(get(l, r, 2*i+1, b, (b+e)/2),
	           get(l, r, 2*i+2, (b+e)/2, e));
}

int h[N], a[N], b[N];
vector<int> add[N];
vector<int> rem[N];
int ql[N], qr[N];
int qans[N];
vector<int> qvec[N];
int n, q;

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,0,n) {
		cin >> h[i] >> a[i] >> b[i];
		if (i + a[i] < n)
			add[i + a[i]].push_back(i);
		if (i + b[i] + 1 < n)
			rem[i + b[i] + 1].push_back(i);
	}
	cin >> q;
	Loop (i,0,q) {
		cin >> ql[i] >> qr[i];
		--ql[i];
		qvec[qr[i]-1].push_back(i);
	}
	init(0, 0, n);
	Loop (i,0,n) {
		for (int j : add[i])
			changei(j, h[j], 0, 0, n);
		for (int j : rem[i])
			changei(j, -1, 0, 0, n);
		int l = max(0ll, i - b[i]);
		int r = min(i, i - a[i] + 1);
		insertr(l, r, h[i], 0, 0, n);
		for (int j : qvec[i])
			qans[j] = get(ql[j], qr[j], 0, 0, n);
	}
	Loop (i,0,q)
		cout << (qans[i] < 0? -1: qans[i]) << '\n';
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 192 ms 34040 KB Output is correct
2 Correct 219 ms 35100 KB Output is correct
3 Correct 145 ms 31960 KB Output is correct
4 Correct 225 ms 35020 KB Output is correct
5 Correct 92 ms 24256 KB Output is correct
6 Correct 214 ms 35020 KB Output is correct
7 Incorrect 201 ms 33796 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

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