oj.uz

Submission #476633

# Submission time Handle Problem Language Result Execution time Memory
476633 2021-09-27T20:23:45 Z cheissmart Two Antennas (JOI19_antennas) C++14
22 / 100
 729 ms 27588 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;
	node() {
		base_mx = lz_mx = sum_mx = -INF;
	}
} 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) {
	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) 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);
		if(op)
			t[v].base_mx = seg_a[pos];
		else
			t[v].base_mx = -INF;
		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 < 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 = min(n - 1, i + b[i]);
			if(L <= R) {
				ev[L].EB(i, true);
				if(R + 1 < n) ev[R + 1].EB(i, false);
			}
		}
		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 = max(0, i - b[i]), R = i - a[i];
			if(R < L) continue;
			upd(L, R + 1, h[i]);
			for(int j:G[i]) {
				assert(r[j] == i);
				cmax(ans[j], qry(l[j], i));
			}
		}
		for(int i = 0; i < n; i++) {
			G[i].clear();
			ev[i].clear();
		}
	};

	solve();
	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]);
	}
	solve();

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

}

Compilation message

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

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 19020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 19020 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 585 ms 26076 KB Output is correct
2 Correct 671 ms 26916 KB Output is correct
3 Correct 432 ms 24444 KB Output is correct
4 Correct 632 ms 26832 KB Output is correct
5 Correct 269 ms 22664 KB Output is correct
6 Correct 621 ms 26824 KB Output is correct
7 Correct 586 ms 25824 KB Output is correct
8 Correct 636 ms 26796 KB Output is correct
9 Correct 88 ms 20372 KB Output is correct
10 Correct 729 ms 26800 KB Output is correct
11 Correct 397 ms 23956 KB Output is correct
12 Correct 656 ms 26836 KB Output is correct
13 Correct 604 ms 27016 KB Output is correct
14 Correct 564 ms 26772 KB Output is correct
15 Correct 577 ms 26008 KB Output is correct
16 Correct 507 ms 25880 KB Output is correct
17 Correct 636 ms 27588 KB Output is correct
18 Correct 579 ms 26412 KB Output is correct
19 Correct 672 ms 26676 KB Output is correct
20 Correct 574 ms 26620 KB Output is correct
21 Correct 533 ms 26632 KB Output is correct
22 Correct 566 ms 26560 KB Output is correct
23 Correct 581 ms 26744 KB Output is correct
24 Correct 529 ms 25352 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 19020 KB Output isn't correct
2 Halted 0 ms 0 KB -