oj.uz

Submission #476629

# Submission time Handle Problem Language Result Execution time Memory
476629 2021-09-27T19:52:54 Z cheissmart Two Antennas (JOI19_antennas) C++14
22 / 100
 810 ms 30704 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++) {
			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 Incorrect 11 ms 22220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 22220 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 652 ms 29212 KB Output is correct
2 Correct 719 ms 29928 KB Output is correct
3 Correct 492 ms 27672 KB Output is correct
4 Correct 739 ms 30020 KB Output is correct
5 Correct 319 ms 25704 KB Output is correct
6 Correct 810 ms 30028 KB Output is correct
7 Correct 675 ms 28948 KB Output is correct
8 Correct 748 ms 29964 KB Output is correct
9 Correct 94 ms 23468 KB Output is correct
10 Correct 789 ms 29968 KB Output is correct
11 Correct 449 ms 27080 KB Output is correct
12 Correct 707 ms 29920 KB Output is correct
13 Correct 693 ms 30208 KB Output is correct
14 Correct 628 ms 29900 KB Output is correct
15 Correct 627 ms 29008 KB Output is correct
16 Correct 578 ms 29064 KB Output is correct
17 Correct 718 ms 30704 KB Output is correct
18 Correct 654 ms 29508 KB Output is correct
19 Correct 677 ms 29804 KB Output is correct
20 Correct 658 ms 29844 KB Output is correct
21 Correct 590 ms 29764 KB Output is correct
22 Correct 640 ms 29628 KB Output is correct
23 Correct 660 ms 29884 KB Output is correct
24 Correct 555 ms 28636 KB Output is correct

Subtask #4
0 / 65.0

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