Submission #377212

#	Time	Username	Problem	Language	Result	Execution time	Memory
377212		Kevin_Zhang_TW	Two Antennas (JOI19_antennas)	C++17	100 / 100	843 ms	42012 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l) == r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif 
const int MAX_N = 200010, MAX_Q = 200010, inf = 1e9;
 
int n, h[MAX_N], a[MAX_N], b[MAX_N];
int q, ql[MAX_Q], qr[MAX_Q], res[MAX_Q];

struct sgt {
	struct node {
		int amn = inf, bmx = -inf, res = -inf;
		void chb(int b) {
			DE(amn, b);
			chmax(bmx, b);
			chmax(res, bmx - amn);
		}
		void cha(int a) {
			bmx = -inf;
			amn = a;
		}
		// a push is required before upd
		void upd(node a, node b) {
			chmax(res, max(a.res, b.res));
			amn = min(a.amn, b.amn);
		}
	};
	int n;
	vector<node> val;
	sgt (int n) : n(n) { val.resize(n<<1); }
	void update(int i) {
		if (i >= n) return;
		push(i);
		val[i].upd(val[i<<1], val[i<<1|1]);
	}
	void push(int i) {
		if (i >= n) return;
		int &b = val[i].bmx;
		if (b == -inf) return;
		val[i<<1].chb(b), val[i<<1|1].chb(b);
		b = -inf;
	}
	void pa(int &i) {
		i += n;
		for (int j = 18;j > 0;--j)
			push(i>>j);
	}
	void modia(int i, int a) {
		pa(i);
		val[i].cha(a);
		for (;i>>=1;)
			update(i);
	}
	void chmxb(int l, int r, int b) {
		pa(l), pa(r);
		int sl = l, sr = r;
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) val[l++].chb(b);
			if (r&1) val[--r].chb(b);
		}
		for (;sl>>=1, sr>>=1;)
			update(sl), update(sr);
	}
	int qry(int l, int r) {
		int res = -inf;
		pa(l), pa(r);
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) chmax(res, val[l++].res);
			if (r&1) chmax(res, val[--r].res);
		}
		return res;
	}
};

vector<pair<int,int>> allq[MAX_N];
void solve() {
	vector<vector<int>> in(n+10), out(n+10);
	for (int i = 0;i < n;++i) {
		int l = i + a[i], r = i + b[i];
		in[ min(n, l) ].pb(i);
		out[ min(n, r) ].pb(i);
	}

	sgt tree(n);

	for (int i = 0;i < n;++i) {
		for (int id : in[i]) {
			DE("modia ", id, h[id]);
			tree.modia(id, h[id]);
		}

		int l = i - b[i], r = i - a[i];
		chmax(l, 0), chmax(r, -1);
		DE(i, l, r, h[i]);
		tree.chmxb(l, r+1, h[i]);

		for (auto [l, id] : allq[i]) {
			chmax(res[id], tree.qry(l, i+1));
		}
		
		for (int id : out[i]) {
			tree.modia(id, inf);
		}

	}
}
 
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n ;
	for (int i = 0;i < n;++i)
		cin >> h[i] >> a[i] >> b[i];
 
	cin >> q;
	for (int i = 0;i < q;++i) {
		cin >> ql[i] >> qr[i], --ql[i], --qr[i];
		allq[ qr[i] ].pb( ql[i], i );

		res[i] = -1;
	}
		
	solve();

	for (int i = 0;i < n;++i) {
		h[i] = inf - h[i];
	}

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

Compilation message (stderr)

antennas.cpp: In member function 'void sgt::node::chb(int)':
antennas.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
antennas.cpp:26:4: note: in expansion of macro 'DE'
   26 |    DE(amn, b);
      |    ^~
antennas.cpp: In function 'void solve()':
antennas.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
antennas.cpp:100:4: note: in expansion of macro 'DE'
  100 |    DE("modia ", id, h[id]);
      |    ^~
antennas.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
antennas.cpp:106:3: note: in expansion of macro 'DE'
  106 |   DE(i, l, r, h[i]);
      |   ^~

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65