Submission #613681

#	Time	Username	Problem	Language	Result	Execution time	Memory
613681		amunduzbaev	Two Antennas (JOI19_antennas)	C++17	0 / 100	3089 ms	2772 KiB

antennas

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
#define sow cerr<<"here"<<endl;
 
const int inf = 1e9 + 5;
const int N = 2005;
const int B = 50;
const int B_ = N / B + 2;
 
struct ST{
	int mx[B << 2], mn[B << 2];
	ST(){
		for(int i=0;i<(B << 2);i++) mn[i] = inf, mx[i] = -inf;
	}
	
	void set(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx){
			if(v == -1) mn[x] = inf, mx[x] = -inf;
			else mn[x] = mx[x] = v;
			return;
		} int m = (lx + rx) >> 1;
		if(i <= m) set(i, v, lx, m, x << 1);
		else set(i, v, m + 1, rx, x << 1 | 1);
		mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
		mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
	}
	
	ar<int, 2> get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l){
			return {inf, -inf};
		} if(lx >= l && rx <= r){
			return {mn[x], mx[x]};
		} int m = (lx + rx) >> 1;
		auto L = get(l, r, lx, m, x << 1), R = get(l, r, m + 1, rx, x << 1 | 1);
		return {min(L[0], R[0]), max(L[1], R[1])};
	}
}tree;
 
vector<int> Q[N];
int pref[B_][N], suff[B_][N];
int h[N], a[N], b[N];
int l[N], r[N], ans[B_][B][B];
 
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; 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];
	}
	
	memset(pref, -1, sizeof pref);
	memset(suff, -1, sizeof suff);
	memset(ans, -1, sizeof ans);
	for(int g=0;g * B<n;g++){
		int L = g * B, R = min(n, (g + 1) * B);
		vector<ar<int, 2>> t;
		for(int i=L;i<R;i++){
			t.push_back({i + a[i], i + 1});
			t.push_back({i + b[i] + 1, -i - 1});
		}
		
		sort(t.begin(), t.end());
		multiset<int> ss;
		int j = 0;
		for(int i=L;i<n;i++){
			while(j < (int)t.size() && t[j][0] <= i){
				if(t[j][1] > 0){
					ss.insert(h[t[j][1] - 1]);
				} else {
					ss.erase(ss.find(h[-t[j][1] - 1]));
				} j++;
			}
			
			if(i) pref[g][i] = pref[g][i-1];
			if(i - b[i] <= L && R - 1 <= i - a[i]){
				if(!ss.empty()){
					pref[g][i] = max(pref[g][i], abs(*--ss.end() - h[i]));
					pref[g][i] = max(pref[g][i], abs(*ss.begin() - h[i]));
				}
			} else {
				int l_ = max(i - b[i], L), r_ = min(i - a[i], R - 1);
				for(int j=l_;j<=r_;j++){
					if(j + a[j] <= i && i <= j + b[j]){
						pref[g][i] = max(pref[g][i], abs(h[i] - h[j]));
					}
				}
			}
		}
		
		t.clear();
		for(int i=L;i<R;i++){
			t.push_back({i - a[i], i + 1});
			t.push_back({i - b[i] - 1, -i - 1});
		}
		
		sort(t.rbegin(), t.rend());
		ss.clear(), j = 0;
		for(int i=R-1;~i;i--){
			while(j < (int)t.size() && t[j][0] >= i){
				if(t[j][1] > 0){
					ss.insert(h[t[j][1] - 1]);
				} else {
					ss.erase(ss.find(h[-t[j][1] - 1]));
				} j++;
			}
			
			suff[g][i] = suff[g][i+1];
			if(i + a[i] <= L && R - 1 <= i + b[i]){
				if(!ss.empty()){
					suff[g][i] = max(suff[g][i], abs(*--ss.end() - h[i]));
					suff[g][i] = max(suff[g][i], abs(*ss.begin() - h[i]));
				}
			} else {
				int l_ = max(i + a[i], L), r_ = min(i + b[i], R - 1);
				for(int j=l_;j<=r_;j++){
					if(j - b[j] <= i && i <= j - a[j]){
						suff[g][i] = max(suff[g][i], abs(h[i] - h[j]));
					}
				}
			}
		}
		
		for(int i=R-1;i>=L;i--){
			//~ seg[0][g][i-L][i-L] = seg[1][g][i-L][i-L] = h[i];
			for(int j=i+1;j<R;j++){
				//~ seg[0][g][i-L][j-L] = min(seg[0][g][i-L][j-L-1], h[j]);
				//~ seg[1][g][i-L][j-L] = max(seg[1][g][i-L][j-L-1], h[j]);
				ans[g][i-L][j-L] = max(ans[g][i+1-L][j-L], ans[g][i-L][j-L-1]);
				if(i + a[i] <= j && j <= i + b[i] && j - b[j] <= i && i <= j - a[j]){
					ans[g][i-L][j-L] = max(ans[g][i-L][j-L], abs(h[i] - h[j]));
				}
			}
		}
	}
	
	for(int j=0;j<q;j++){
		l[j]--, r[j]--;
		int bl = l[j] / B, br = r[j] / B, res = -1;
		if(bl == br){
			int L = bl * B;
			cout<<ans[bl][l[j] - L][r[j] - L]<<"\n";
			continue;
		}
		
		for(int i=bl + 1;i<br;i++){
			res = max(res, pref[i][r[j]]);
			res = max(res, suff[i][l[j]]);
		}
		
		res = max(res, pref[br][r[j]]);
		res = max(res, suff[bl][l[j]]);
		int L = br * B, R = (bl + 1) * B - 1;
		for(int i=l[j];i<=R;i++){
			int l_ = max(i + a[i], L), r_ = min(i + b[i], r[j]);
			if(l_ <= r_){
				Q[l_].push_back(i);
				//~ res = max(res, abs(h[i] - seg[0][br][l_-L][r_-L]));
				//~ res = max(res, abs(h[i] - seg[1][br][l_-L][r_-L]));
				Q[r_ + 1].push_back(-i - 1);
			}
		}
		for(int i=L;i<=r[j];i++){
			for(auto k : Q[i]){
				if(k >= 0) tree.set(k - l[j], h[k]);
				else tree.set(-k - 1 - l[j], -1);
			} Q[i].clear();
			int l_ = max(i - b[i], l[j]), r_ = min(i - a[i], R);
			if(l_ <= r_){
				auto sg = tree.get(l_ - l[j], r_ - l[j]);
				if(sg[1] >= 0){
					res = max({res, abs(h[i] - sg[0]), abs(h[i] - sg[1])});
				}
			}
		}
		for(auto k : Q[r[j] + 1]){
			if(k >= 0) tree.set(k - l[j], h[k]);
			else tree.set(-k - 1 - l[j], -1);
		} Q[r[j] + 1].clear();
		cout<<res<<"\n";
	}
}

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