oj.uz

Submission #476626

# Submission time Handle Problem Language Result Execution time Memory
476626 2021-09-27T19:37:56 Z cheissmart Two Antennas (JOI19_antennas) C++14
22 / 100
 1489 ms 30708 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("trapv")
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
	cerr << to_string(h);
	if(sizeof ...(t)) cerr << ", ";
	DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif

const int INF = 1e9 + 7, N = 2e5 + 7;
void cmax(int& a, int b) {
	a = max(a, b);
}

int h[N], a[N], b[N], l[N], r[N], ans[N];
vi G[N];

int n;

int seg_a[N];

struct node {
	int base_mx, lz_mx, sum_mx;
	bool active;
	node() {
		base_mx = lz_mx = sum_mx = -INF;
		active = true;
	}
	int Base_mx() {
		if(!active) return -INF;
		return base_mx;
	}
} t[N * 4];

void pull(int v) {
	t[v].base_mx = max(t[v * 2].Base_mx(), t[v * 2 + 1].Base_mx());
	t[v].sum_mx = max(t[v * 2].sum_mx, t[v * 2 + 1].sum_mx);
}

void apply(int v, int x) {
	if(!t[v].active)
		return;
	cmax(t[v].sum_mx, t[v].base_mx + x);
	cmax(t[v].lz_mx, x);
}

void push(int v) {
	apply(v * 2, t[v].lz_mx);
	apply(v * 2 + 1, t[v].lz_mx);
	t[v].lz_mx = -INF;
}

void build(int v = 1, int tl = 0, int tr = n) {
	t[v] = node();
	if(tr - tl == 1) {
		t[v].active = false;
		t[v].base_mx = seg_a[tl];
		return;
	}
	int tm = (tl + tr) / 2;
	build(v * 2, tl, tm);
	build(v * 2 + 1, tm, tr);
	pull(v);
}

void activate(int pos, bool op, int v = 1, int tl = 0, int tr = n) {
	if(tr - tl == 1) {
		assert(tl == pos);
		t[v].active = op;
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	if(pos < tm)
		activate(pos, op, v * 2, tl, tm);
	else
		activate(pos, op, v * 2 + 1, tm, tr);
	pull(v);
}

void upd(int l, int r, int x, int v = 1, int tl = 0, int tr = n) {
	if(l <= tl && tr <= r) {
		apply(v, x);
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	if(l < tm)
		upd(l, r, x, v * 2, tl, tm);
	if(r > tm)
		upd(l, r, x, v * 2 + 1, tm, tr);
	pull(v);
}

int qry(int l, int r, int v = 1, int tl = 0, int tr = n) {
	if(l <= tl && tr <= r)
		return t[v].sum_mx;
	push(v);
	int tm = (tl + tr) / 2;
	int ans = -INF;
	if(l < tm)
		cmax(ans, qry(l, r, v * 2, tl, tm));
	if(r > tm)
		cmax(ans, qry(l, r, v * 2 + 1, tm, tr));
	return ans;
}

V<pair<int, bool>> ev[N];

signed main()
{
	IO_OP;
	
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> h[i] >> a[i] >> b[i];
	}
	int q;
	cin >> q;
	for(int i = 0; i < q; i++) {
		cin >> l[i] >> r[i];
		l[i]--, r[i]--;
		ans[i] = -1;
	}

	auto solve = [&] () {
		for(int i = 0; i < n; i++) {
			seg_a[i] = -h[i];
		}
		build();
		for(int i = 0; i < n; i++) {
			for(auto[x, y]:ev[i]) {
				activate(x, y);
			}
			int L = i - b[i], R = i - a[i];
			if(R < 0) continue;
			L = max(L, 0);
			upd(L, R + 1, h[i]);
			for(int j:G[i]) {
				assert(r[j] == i);
				cmax(ans[j], qry(l[j], i));
			}
		}
	};

	auto solve1 = [&] () {
		for(int i = 0; i < q; i++) {
			assert(l[i] < r[i]);
			G[r[i]].PB(i);
		}
		for(int i = 0; i < n; i++) {
			int L = i + a[i], R = i + b[i];
			if(L < n) {
				R = min(R, n - 1);
				ev[L].EB(i, true);
				if(R + 1 < n) ev[R + 1].EB(i, false);
			}
		}
		solve();
		for(int i = 0; i < n; i++)
			h[i] *= -1;
		solve();
		for(int i = 0; i < n; i++) {
			G[i].clear();
			ev[i].clear();
		}
	};

	solve1();
	reverse(h, h + n), reverse(a, a + n), reverse(b, b + n);
	for(int i = 0; i < q; i++) {
		l[i] = n - l[i] - 1, r[i] = n - r[i] - 1;
		swap(l[i], r[i]);
	}
	solve1();

	for(int i = 0; i < q; i++)
		cout << ans[i] << '\n';

}

Compilation message

antennas.cpp: In lambda function:
antennas.cpp:153:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  153 |    for(auto[x, y]:ev[i]) {
      |            ^

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22220 KB Output is correct
2 Incorrect 15 ms 22268 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22220 KB Output is correct
2 Incorrect 15 ms 22268 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1342 ms 29312 KB Output is correct
2 Correct 1440 ms 29996 KB Output is correct
3 Correct 883 ms 27696 KB Output is correct
4 Correct 1387 ms 29964 KB Output is correct
5 Correct 637 ms 25916 KB Output is correct
6 Correct 1452 ms 30040 KB Output is correct
7 Correct 1128 ms 28972 KB Output is correct
8 Correct 1391 ms 30060 KB Output is correct
9 Correct 167 ms 23476 KB Output is correct
10 Correct 1383 ms 29972 KB Output is correct
11 Correct 808 ms 27096 KB Output is correct
12 Correct 1407 ms 29972 KB Output is correct
13 Correct 1389 ms 30276 KB Output is correct
14 Correct 1213 ms 30008 KB Output is correct
15 Correct 1230 ms 29136 KB Output is correct
16 Correct 1072 ms 29064 KB Output is correct
17 Correct 1489 ms 30708 KB Output is correct
18 Correct 1269 ms 29544 KB Output is correct
19 Correct 1381 ms 29744 KB Output is correct
20 Correct 1426 ms 29820 KB Output is correct
21 Correct 1288 ms 29736 KB Output is correct
22 Correct 1406 ms 29672 KB Output is correct
23 Correct 1400 ms 29848 KB Output is correct
24 Correct 1223 ms 28524 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22220 KB Output is correct
2 Incorrect 15 ms 22268 KB Output isn't correct
3 Halted 0 ms 0 KB -