Submission #1267976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267976		SmuggingSpun	Two Antennas (JOI19_antennas)	C++20	100 / 100	547 ms	41176 KiB

antennas

#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
template<class T>void minimize(T& a, T b){
	if(a > b){
		a = b;
	}
}
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
const int lim = 25e4 + 5;
int n, q, h[lim], a[lim], b[lim];
namespace sub1{
	void solve(){
		for(int _ = 0; _ < q; _++){
			int l, r, ans = -1;
			cin >> l >> r;
			for(int i = l; i < r; i++){
				for(int j = r; j > i; j--){
					int d = j - i;
					if(max(a[i], a[j]) <= d && min(b[i], b[j]) >= d){
						maximize(ans, abs(h[i] - h[j]));
					}
				}
			}
			cout << ans << "\n";
		}
	}
}
namespace sub2{
	void solve(){
		vector<vector<int>>f(n + 1, vector<int>(n + 1, -1));
		for(int i = 1; i < n; i++){
			for(int l = 1; true; l++){
				int r = l + i;
				f[l][r] = max({f[l][r - 1], f[l + 1][r], max(a[l], a[r]) <= i && min(b[l], b[r]) >= i ? abs(h[l] - h[r]) : -1});
				if(r == n){
					break;
				}
			}
		}
		for(int _ = 0; _ < q; _++){
			int l, r;
			cin >> l >> r;
			cout << f[l][r] << "\n";
		}
	}
}
namespace sub34{
	const int INF = 1e9 + 5;
	struct Data{
		int max_h, min_h, max_delta, laz_ma, laz_mi;
		Data(){
			max_h = laz_ma = max_delta = -(min_h = laz_mi = INF);
		}
	};
	Data merge(Data a, Data b){
		Data c;
		c.max_h = max(a.max_h, b.max_h);
		c.min_h = min(a.min_h, b.min_h);
		c.max_delta = max(a.max_delta, b.max_delta);
		return c;
	}
	Data st[lim << 2];
	void refine_delta(int id, int H, bool min_la, bool max_la){
		if(abs(H) == INF){
			return;
		}
		maximize(st[id].max_delta, max(H - st[id].min_h, st[id].max_h - H));
		if(min_la){
			minimize(st[id].laz_mi, H);
		}
		if(max_la){
			maximize(st[id].laz_ma, H);
		}
	}
	void push_down(int id){
		refine_delta(id << 1, st[id].laz_mi, true, false);
		refine_delta(id << 1, st[id].laz_ma, false, true);
		refine_delta(id << 1 | 1, st[id].laz_mi, true, false);
		refine_delta(id << 1 | 1, st[id].laz_ma, false, true);
		st[id].laz_ma = -(st[id].laz_mi = INF);
	}
	void update_h(int id, int l, int r, int p, int x){
		if(l == r){
			if(x == 0){
				st[id].max_h = -(st[id].min_h = INF);
			}
			else{
				st[id].min_h = st[id].max_h = x;				
			}
			return;
		}
		int m = (l + r) >> 1;
		push_down(id);
		if(m < p){
			update_h(id << 1 | 1, m + 1, r, p, x);
		}
		else{
			update_h(id << 1, l, m, p, x);
		}
		st[id] = merge(st[id << 1], st[id << 1 | 1]);
	}
	void update(int id, int l, int r, int u, int v, int H){
		if(l > v || r < u){
			return;
		}
		if(u <= l && v >= r){
			refine_delta(id, H, true, true);
			return;
		}
		int m = (l + r) >> 1;
		push_down(id);
		update(id << 1, l, m, u, v, H);
		update(id << 1 | 1, m + 1, r, u, v, H);
		st[id] = merge(st[id << 1], st[id << 1 | 1]);
	}
	Data get(int id, int l, int r, int u, int v){
		if(l > v || r < u){
			return Data();
		}
		if(u <= l && v >= r){
			return st[id];
		}
		int m = (l + r) >> 1;
		push_down(id);
		return merge(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
	}
	vector<pair<int, int>>query[lim];
	vector<int>event[lim];
	int ans[lim];
	void solve(){
		for(int i = 0; i < q; i++){
			int l, r;
			cin >> l >> r;
			query[r].emplace_back(l, i);
		}
		for(int r = 1; r <= n; r++){
			for(int& x : event[r]){
				if(x < 0){
					update_h(1, 1, n, -x, 0);
				}
				else{
					update_h(1, 1, n, x, h[x]);
				}
			}
			int L = max(1, r - b[r]), R = r - a[r];
			if(L <= R){
				update(1, 1, n, L, R, h[r]);
			}
			for(int i = 0; i < query[r].size(); i++){
				ans[query[r][i].second] = get(1, 1, n, query[r][i].first, r).max_delta;
			}
			if(r + a[r] <= n){
				event[r + a[r]].emplace_back(r);
				event[min(r + b[r], n) + 1].emplace_back(-r);
			}
		}
		for(int i = 0; i < q; i++){
			cout << max(ans[i], -1) << "\n";
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> h[i] >> a[i] >> b[i];
	}
	cin >> q;
	if(max(n, q) <= 300){
		sub1::solve();
	}
	else if(n <= 2000){
		sub2::solve();
	}
	else{
		sub34::solve();
	}
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:170:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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