Submission #1297964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297964		TrieTr	Two Antennas (JOI19_antennas)	C++20	13 / 100	57 ms	7280 KiB

antennas

#include<bits/stdc++.h>
using namespace std;

void local() {
    #define taskname ""
    if (fopen(taskname".inp", "r")) {
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
}

#define ll long long
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

template<class X, class Y> bool mini(X &a, const Y &b) {return (a > b) ? a = b, true : false;}
template<class X, class Y> bool maxi(X &a, const Y &b) {return (a < b) ? a = b, true : false;}

const int N = 2e5 + 5;

int n;
int h[N], a[N], b[N];
int q;
pair<int, int> que[N];

namespace sub2 {
	bool check() {
		return n <= 2e3;
	}

	struct SegmentTree {
		using T = int;
		vector<T> st;
		int n;
		void init(int n_) {
			n = n_;
			st.assign((n + 5) << 2, -2e9 - 1);
		}
		void update(int x, int v, int l, int r, int id) {
			if(l > x || r < x) return;
			if(l == r) {
				maxi(st[id], v);
				return;
			}
			int mid = (l + r) >> 1;
			update(x, v, l, mid, id << 1); update(x, v, mid + 1, r, id << 1 | 1);
			st[id] = max(st[id << 1], st[id << 1 | 1]);
		}
		T get(int x, int y, int l, int r, int id) {
			if(l > y  || r < x) return -2e9 - 1;
			if(l >= x && r <= y) return st[id];
			int mid = (l + r) >> 1;
			return max(get(x, y, l, mid, id << 1), get(x, y, mid + 1, r, id << 1 | 1));
		}
	};

	vector<pair<int, int>> event[N];
	bool isin(int i, int x, int y) {
		return x <= i && i <= y;
	}
	int ans[N];
	void solve() {
		for(int i = 1; i <= q; i++) {
			auto[l, r] = que[i];
			event[r].emplace_back(l, i);
		}
		SegmentTree T;
		T.init(n);
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j < i; j++) {
				if(isin(abs(i - j), a[j], b[j]) && isin(abs(i - j), a[i], b[i])) {
					T.update(j, abs(h[i] - h[j]), 1, n, 1);
				}
			}
			for(auto[l, id] : event[i]) {
				ans[id] = T.get(l, i, 1, n, 1);
			}
		}
		for(int i = 1; i <= q; i++) cout << (ans[i] == -2e9 - 1 ? -1 : ans[i]) << '\n';
	}
}

namespace sub3 {
	bool check() {
		return n <= 2e3;
	}
	struct SegmentTree {
		using T = pair<int, int>;
		vector<T> st;
		vector<int> lazy;
		int n;
		void init(int n_) {
			n = n_;
			st.assign((n + 5) << 2, make_pair(1e9 + 1, -1e9 - 1));
			lazy.assign((n + 5) << 2, -1);
		}
		T merge(T a, T b) {
			pair<int, int> c;
			c.fi = min(a.fi, b.fi);
			c.se = max(a.se, b.se);
			return c;
		}
		void down(int id) {
			if(lazy[id] == -1) return;
			mini(st[id << 1].fi, lazy[id]);
			maxi(st[id << 1].se, lazy[id]);
			lazy[id << 1] = lazy[id];
			mini(st[id << 1 | 1].fi, lazy[id]);
			maxi(st[id << 1 | 1].se, lazy[id]);
			lazy[id << 1 | 1] = lazy[id];
			lazy[id] = -1;
		}
		void update(int x, int y, int v, int l, int r, int id) {
			if(l > y || r < x) return;
			if(l >= x && r <= y) {
				mini(st[id].fi, v);
				maxi(st[id].se, v);
				lazy[id] = v;
				return;
			}
			int mid = (l + r) >> 1; down(id);
			update(x, y, v, l, mid, id << 1); update(x, y, v, mid + 1, r, id << 1 | 1);
			st[id] = merge(st[id << 1], st[id << 1 | 1]);
		}
		T get(int x, int y, int l, int r, int id) {
			if(l > y  || r < x) return make_pair(1e9 + 1, -1e9 - 1);
			if(l >= x && r <= y) return st[id];
			int mid = (l + r) >> 1; down(id);
			return merge(get(x, y, l, mid, id << 1), get(x, y, mid + 1, r, id << 1 | 1));
		}
	};
	int res[N];
	void solve() {
		/*for(int i = 1; i <= n; i++) {
			T.init(n);
			int res = -1;
			for(int j = i; j <= n; j++) {
				pair<int, int> cur = T.get(
			}
		}*/
	}
}

int main() {
    fastio; local();
    cin >> n;
    for(int i = 1; i <= n; i++) {
    	cin >> h[i] >> a[i] >> b[i];
    }
    cin >> q;
    for(int i = 1; i <= q; i++) {
    	int l, r; cin >> l >> r;
    	que[i] = make_pair(l, r);
    }
    if(sub2::check()) sub2::solve();
}

Compilation message (stderr)

antennas.cpp: In function 'void local()':
antennas.cpp:7:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:8:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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