Submission #514598

#	Time	Username	Problem	Language	Result	Execution time	Memory
514598		fatemetmhr	Two Antennas (JOI19_antennas)	C++17	100 / 100	908 ms	61276 KiB

antennas

//  ~Be name khoda~  //

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'

const int maxn  =  1e6   + 10;
const int maxn5 =  2e5   + 10;
const int maxnt =  8e5   + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;



struct javab{
	ll val1, val2, mn, mx, ans1, ans2;
	javab(){
		val1 = val2 = mn = mx = ans1 = ans2 = -1 * inf;
		return;	
	}
} seg[maxnt];


int a[maxn5], b[maxn5], h[maxn5], l[maxn5], r[maxn5];
vector <pair<int, pair<int, int>>> eve;
vector <int> req;
ll out[maxn5];

void shift(int, int, int);

inline bool cmp(int i, int j){return l[i] > l[j];}

inline void recalc(int v){
	seg[v].ans1 = max(seg[v].ans1, seg[v].val1 + seg[v].mn);
	seg[v].ans2 = max(seg[v].ans2, seg[v].val2 + seg[v].mx);
	return;
}

inline javab multi(javab a, javab b, javab c, bool ty){
	javab ret;
	ret.val1 = max(b.val1, c.val1);
	ret.val2 = max(b.val2, c.val2);
	ret.ans1 = max(b.ans1, c.ans1);
	ret.ans2 = max(b.ans2, c.ans2);
	if(ty){
		ret.ans1 = max(ret.ans1, a.ans1);
		ret.ans2 = max(ret.ans2, a.ans2);
	}
	return ret;
}

inline void setval(int l, int r, int ind, ll va1, ll va2, int v){
	if(r - l == 1){
		seg[v].mn = seg[v].mx = -1 * inf;
		seg[v].val1 = va1;
		seg[v].val2 = va2;
		//recalc(v);
		//cout << "ok setval " << l << ' ' << r << ' ' << seg[v].val1 << ' ' << seg[v].ans1 << endl;
		return;
	}
	int mid = (l + r) >> 1; shift(v, l, r);
	if(ind < mid)
		setval(l, mid, ind, va1, va2, v * 2);
	else
		setval(mid, r, ind, va1, va2, v * 2 + 1);
		
	seg[v] = multi(seg[v], seg[v * 2], seg[v * 2 + 1], true);
	//cout << "righttt " << l << ' ' << r << ' ' << seg[v].ans1 << ' ' << seg[v].mn << endl;
	return;
}

inline void setmax(int l, int r, int lq, int rq, ll va1, ll va2, int v){
	//cout << "em vel " << l << ' ' << r << ' ' << lq << ' ' << rq << endl;
	if(rq <= l || r <= lq)
		return;
	if(lq <= l && r <= rq){
		seg[v].mn = max(seg[v].mn, va1);
		seg[v].mx = max(seg[v].mx, va2);
		recalc(v);
		// << ' ' << l << ' ' << r << ' ' << va1 << ' ' << seg[v].ans1 << ' ' << seg[v].mn << ' ' << seg[v].val1 << endl;
		return;
	}
	int mid = (l + r) >> 1; shift(v, l, r);
	setmax(l, mid, lq, rq, va1, va2, v * 2);
	setmax(mid, r, lq, rq, va1, va2, v * 2 + 1);
	seg[v] = multi(seg[v], seg[v * 2], seg[v * 2 + 1], true);
	return;
}

inline ll get_max(int l, int r, int lq, int rq, int v){
	//cout << "hey getting max! " << endl;
	if(rq <= l || r <= lq)
		return -1 * inf;
	if(lq <= l && r <= rq){
		//<< l << ' ' << r << ' ' << seg[v].ans1 << ' ' << seg[v].val1 << ' ' << seg[v].mn << endl;
		return max(seg[v].ans1, seg[v].ans2);
	}
	int mid = (l + r) >> 1; shift(v, l, r);
	return max(get_max(l, mid, lq, rq, v * 2), get_max(mid, r, lq, rq, v * 2 + 1));
}	

inline void shift(int v, int l, int r){
	int mid = (l + r) >> 1;
	setmax(l, mid, l, mid, seg[v].mn, seg[v].mx, v * 2);
	setmax(mid, r, mid, r, seg[v].mn, seg[v].mx, v * 2 + 1);
	seg[v].mn = seg[v].mx = -1 * inf;
	return;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int n; cin >> n;
	for(int i = 0; i < n; i++){
		cin >> h[i] >> a[i] >> b[i];
		eve.pb({i, {0, i}});
		eve.pb({i - a[i], {1, i}});
		eve.pb({i - b[i] - 1, {2, i}});
	}
	
	sort(all(eve));
	
	int q; cin >> q;
	for(int i = 0; i < q; i++){
		cin >> l[i] >> r[i];
		l[i]--;
		r[i]--;
		req.pb(i);
	}
	sort(all(req), cmp); // az l bozorg be koochak
	
	for(auto i : req){
		//cout << "aha " << l[i] << ' ' << eve.size() << ' ' << eve.back().fi << endl;
		while(!eve.empty() && eve.back().fi >= l[i]){
			int ty = eve.back().se.fi, id = eve.back().se.se;
			eve.pop_back();
			if(ty == 0){
				setmax(0, n, min(n, id + a[id]), min(n, id + b[id] + 1), -h[id], h[id], 1);
				setval(0, n, id, -1 * inf, -1 * inf, 1);
			}
			if(ty == 1){
				setval(0, n, id, h[id], -1 * h[id], 1);
			}
			if(ty == 2){
				setval(0, n, id, -1 * inf, -1 * inf, 1);
			}
			//cout << "after event of " << ty << ' ' << id << ' ' << seg[1].ans1 << ' ' << seg[1].ans2 << endl;
		}
		out[i] = get_max(0, n, l[i], r[i] + 1, 1);
	}
	
	for(int i = 0; i < q; i++)
		cout << (out[i] < 0 ? -1 : out[i]) << '\n';
	
}

/*
20
260055884 2 15
737689751 5 5
575359903 1 15
341907415 14 14
162026576 9 19
55126745 10 19
95712405 11 14
416027186 8 13
370819848 11 14
629309664 4 13
822713895 5 15
390716905 13 17
577166133 8 19
195931195 10 17
377030463 14 17
968486685 11 19
963040581 4 10
566835557 1 12
586336111 6 16
385865831 8 9
1
1 20

*/

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