Submission #1008802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008802		PoPularPlusPlus	Two Antennas (JOI19_antennas)	C++17	100 / 100	390 ms	51288 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define vf first 
#define vs second
const int mod = 1000000007;
 
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

struct item{
	int mx , mn , mx_out , mn_out , ans;
};

struct Seg{
	vector<item> v;
	vector<int> lazy_mn , lazy_mx;
	int siz;

	item nutral = {-1 , 1000000005 , -1 , 1000000005 , -1000000000};

	item merge(item a , item b){
		item res = nutral;
		//res.mn = max(a.mn , b.mn);
		//res.mx = min(a.mx , b.mx);
		res.ans = max(a.ans , b.ans);
		res.mx_out = max(a.mx_out , b.mx_out);
		res.mn_out = min(a.mn_out , b.mn_out);
		return res;
	}

	void init(int n){
		siz = 1;
		while(siz < n)siz*=2;

		v.assign(siz * 2 , nutral);
		lazy_mx.assign(siz * 2 , -1);
		lazy_mn.assign(siz*2 , 1000000005);
	}

	void push(int x){
		lazy_mn[2*x+1] = min(lazy_mn[2*x+1] , lazy_mn[x]);
		lazy_mn[2*x+2] = min(lazy_mn[2*x+2] , lazy_mn[x]);
		lazy_mx[2*x+1] = max(lazy_mx[2*x+1] , lazy_mx[x]);
		lazy_mx[2*x+2] = max(lazy_mx[2*x+2] , lazy_mx[x]);
		//v[2*x+2].mn = min(v[2*x+2].mn , v[x].mn);
		//v[2*x+1].mx = max(v[2*x+1].mx , v[x].mx);
		//v[2*x+2].mx = max(v[2*x+2].mx , v[x].mx);
		v[2*x+1].ans = max({v[2*x+1].ans , v[2*x+1].mx_out - lazy_mn[x] , lazy_mx[x] - v[2*x+1].mn_out});
		v[2*x+2].ans = max({v[2*x+2].ans , v[2*x+2].mx_out - lazy_mn[x] , lazy_mx[x] - v[2*x+2].mn_out});
		lazy_mn[x] = 1000000005;
		lazy_mx[x] = -1;
	}

	void build(int i , pair<int,int> val , int x , int lx , int rx){
		if(rx - lx == 1){
			v[x].mn_out = val.vf;
			v[x].mx_out = val.vs;
			return;
		}
		push(x);
		int m = (lx + rx)/2;
		if(i < m)build(i , val , 2 * x + 1 ,lx , m);
		else build(i , val, 2 * x + 2 , m , rx);
		v[x] = merge(v[2 * x + 1] , v[2 * x + 2]);
	}

	void build(int i , pair<int,int> val){
		build(i , val , 0 , 0 , siz);
	}

	void set(int l , int r, int val, int x , int lx, int rx){
		if(r <= lx || rx <= l)return;
		if(lx >= l && rx <= r){
			lazy_mn[x] = min(lazy_mn[x] , val);
			lazy_mx[x] = max(lazy_mx[x] , val);
			//v[x].mn = min(v[x].mn , val);
			//v[x].mx = max(v[x].mx , val);
			v[x].ans = max({v[x].ans , v[x].mx_out - val , val - v[x].mn_out});
			//cout << lx << ' ' << rx << ' ' << val << ' ' << v[x].mx_out << ' ' << v[x].mn_out << ' ' << v[x].ans << '\n';
			return;
		}

		push(x);
		int m = (lx + rx)/2;
		set(l , r , val , 2 * x + 1, lx , m);
		set(l , r , val , 2 * x + 2 , m , rx);
		v[x] = merge(v[2 * x + 1] , v[2 * x + 2]);
	}

	void set(int l , int r , int val){
		set(l , r , val , 0 , 0 , siz);
	}

	int range_op(int l , int r , int x , int lx, int rx){
		if(rx <= l || r <= lx)return nutral.ans;
		if(lx >= l && rx <= r){
			//cout << lx << ' ' << rx << ' ' << v[x].mx_out << ' ' << v[x].mn_out << ' ' << lazy_mx[x] << ' ' << lazy_mn[x] << ' ' << v[x].ans << '\n';
			return v[x].ans;
		}

		push(x);
		int m = (lx + rx)/2;
		return max(range_op(l , r , 2 * x + 1 , lx , m) , range_op(l , r , 2 * x + 2 , m , rx));
	}

	int range_op(int l ,int r){
		return range_op(l , r , 0 , 0 ,siz);
	}
};

void solve(){
	int n;
	cin >> n;
	vector<int> h(n);
	int a[n] , b[n];
	for(int i = 0; i < n; i++){
		cin >> h[i] >> a[i] >> b[i];
	}

	Seg st;
	st.init(n);

	int q;
	cin >> q;
	int ans[q];
	vector<int> in[n + 1] , out[n + 1] , right[n + 1];
	vector<pair<int,int>> queries;
	for(int tp = 0; tp < q; tp++){
		int l , r;
		cin >> l >> r;
		l--;
		r--;
		queries.pb(mp(l,r));
		right[r].pb(tp);
	}

	for(int i = 0; i < n; i++){
		in[min(n , i + a[i])].pb(i);
		out[min(n , i + b[i] + 1)].pb(i);
	}

	memset(ans,-1,sizeof ans);

	for(int i = 0; i < n; i++){
		for(int j : in[i]){
			st.build(j , mp(h[j],h[j]));
		}

		for(int j : out[i]){
			st.build(j , mp(1e9 , -1));
		}

		if(i - a[i] >= 0){
			st.set(max(0 , i - b[i]) , i - a[i] + 1 , h[i]);
		}

		for(int j : right[i]){
			ans[j] = st.range_op(queries[j].vf , queries[j].vs + 1);
		}
	}

	for(int i = 0 ; i < q; i++){
		if(ans[i] < 0){
			cout << -1 << '\n';
		}
		else cout << ans[i] << '\n';
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	//int t;
	//cin >> t;
	//while(t--)
		solve();
}

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