Submission #1221384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221384		PenguinsAreCute	Two Antennas (JOI19_antennas)	C++17	22 / 100	175 ms	13520 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
struct seg {
	int n;
	vector<int> v;
	seg(int _n): n(_n), v(2*_n,-1e9-5) {}
	void up(int x, int u) {
		for(v[x+=n]=u;x>>=1;)
			v[x]=max(v[x<<1],v[x<<1|1]);
	}
	int qry(int l, int r) {
		int ans = -1e9-5;
		for(l+=n,r+=n+1;l<r;l>>=1,r>>=1) {
			if(l&1)
				ans=max(ans,v[l++]);
			if(r&1)
				ans=max(ans,v[--r]);
		}
		return ans;
	}
};
int main() {
	int n;
	cin >> n;
	vector<int> h(n), a(n), b(n);
	for(int i=0;i<n;i++)
		cin >> h[i] >> a[i] >> b[i];
	int ans = -1;
	vector<vector<int>> upd(n);
	seg maxH(n), minH(n);
	for(int i=0;i<n;i++) {
		if(i+a[i]<n)
			upd[i+a[i]].push_back(i);
		if(i+b[i]+1<n)
			upd[i+b[i]+1].push_back(~i);
		for(auto j: upd[i])
			if(j>=0) {
				maxH.up(j,h[j]);
				minH.up(j,-h[j]);
			} else {
				maxH.up(~j,-1e9-5);
				minH.up(~j,-1e9-5);
			}
		if(a[i] <= i)
			ans = max({ans,maxH.qry(max(0,i-b[i]),i-a[i])-h[i],h[i]+minH.qry(max(0,i-b[i]),i-a[i])});
	}
	cout << max(-1,ans) << "\n";
}

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