Submission #376959

#	Time	Username	Problem	Language	Result	Execution time	Memory
376959		pit4h	Two Antennas (JOI19_antennas)	C++14	100 / 100	858 ms	43624 KiB

antennas

#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
using namespace std;
using pii = pair<int, int>;

const int MAXN = 2e5+1, INF = 1e9+1;
int n, q, h[MAXN], a[MAXN], b[MAXN];
int ans[MAXN];
vector<int> add[MAXN], del[MAXN];
vector<pii> queries[MAXN];

const int base = (1<<18);
pii treeL[2*base+1], push[2*base+1];
int tree[2*base+1];
int treeMin[2*base+1], treeMax[2*base+1];

int get_min(int x) {
	return treeMin[x];
}
int get_max(int x) {
	return treeMax[x];
}
int eval(int id) {
	if(get_min(id)==INF || treeL[id].st==0) return -1;
	int res = max(abs(get_max(id) - treeL[id].st), abs(treeL[id].nd - get_min(id)));
	return res;
}
void upd(int x, int val) {
	if(val==0) return;
	if(treeL[x].st==0) treeL[x].st = val;
	treeL[x].st = min(treeL[x].st, val);
	treeL[x].nd = max(treeL[x].nd, val);
	tree[x] = max(tree[x], eval(x));
}
void insR(int x, pii val, int id=1, int rl=0, int rr=base-1) {
	if(rl > x || rr < x) return;
	tree[id] = max(tree[id], eval(id));
	//treeR[id].insert(val);
	//updm(id);
	if(rl==x && rr==x) {
		treeMin[id] = treeMax[id] = val.st;
		treeL[id].st = treeL[id].nd = 0;
		return;
	}
	upd(id*2, treeL[id].st), upd(id*2, treeL[id].nd);
	upd(id*2+1, treeL[id].st), upd(id*2+1, treeL[id].nd);
	treeL[id].st = treeL[id].nd = 0;

	insR(x, val, id*2, rl, (rl+rr)/2);
	insR(x, val, id*2+1, (rl+rr)/2+1, rr);
	tree[id] = max(tree[id*2], tree[id*2+1]);
	treeMin[id] = min(treeMin[id*2], treeMin[id*2+1]); //.
	treeMax[id] = max(treeMax[id*2], treeMax[id*2+1]); //.
}
void delR(int x, pii val, int id=1, int rl=0, int rr=base-1) {
	if(rl > x || rr < x) return;
	//treeR[id].erase(val);
	//updm(id);
	if(rl==x && rr==x) {
		treeMin[id] = INF; //.
		treeMax[id] = 0; //.
		return;
	}
	upd(id*2, treeL[id].st), upd(id*2, treeL[id].nd);
	upd(id*2+1, treeL[id].st), upd(id*2+1, treeL[id].nd);

	delR(x, val, id*2, rl, (rl+rr)/2);
	delR(x, val, id*2+1, (rl+rr)/2+1, rr);
	tree[id] = max(tree[id*2], tree[id*2+1]);
	treeMin[id] = min(treeMin[id*2], treeMin[id*2+1]); //.
	treeMax[id] = max(treeMax[id*2], treeMax[id*2+1]); //.	
}

void insL(int l, int r, int val, int id=1, int rl=0, int rr=base-1) {
	if(l > rr || r < rl) return;
	if(l<=rl && r>=rr) {
		upd(id, val);
		return;
	}
	upd(id*2, treeL[id].st), upd(id*2, treeL[id].nd);
	upd(id*2+1, treeL[id].st), upd(id*2+1, treeL[id].nd);

	insL(l, r, val, id*2, rl, (rl+rr)/2);
	insL(l, r, val, id*2+1, (rl+rr)/2+1, rr);

	tree[id] = max(tree[id*2], tree[id*2+1]);
}
int qry(int l, int r, int id=1, int rl=0, int rr=base-1) {
	if(l > rr || r < rl) return -1;
	if(l<=rl && r>=rr) {
		//return max(tree[id], eval(id));
		return tree[id];
	}
	upd(id*2, treeL[id].st), upd(id*2, treeL[id].nd);
	upd(id*2+1, treeL[id].st), upd(id*2+1, treeL[id].nd);

	return max(qry(l, r, id*2, rl, (rl+rr)/2), qry(l, r, id*2+1, (rl+rr)/2+1, rr));
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	for(int i=0; i<2*base; ++i) {
		tree[i] = -1;
		treeMin[i] = INF;
	}

	cin>>n;
	for(int i=0; i<n; ++i) {
		cin>>h[i]>>a[i]>>b[i];
		if(i-a[i]>=0) {
			add[i-a[i]].push_back(i);
			del[max(0, i-b[i])].push_back(i);
		}
	}
	cin>>q;
	for(int i=0; i<q; ++i) {
		int l, r; 
		cin>>l>>r;
		queries[l-1].push_back(mp(r-1, i));
		ans[i] = -1;
	}

	for(int i=n-1; i>=0; --i) {
		for(int j: add[i]) {
			insR(j, mp(h[j], j));	
		}

		if(i+a[i] < n) {
			insL(i+a[i], min(n-1, i+b[i]), h[i]);
		}
		for(auto& [j, id]: queries[i]) {
			ans[id] = qry(i, j);
		}

		for(int j: del[i]) {
			delR(j, mp(h[j], j));
		}
	}


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

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:132:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  132 |   for(auto& [j, id]: queries[i]) {
      |             ^

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