Submission #132119

#	Time	Username	Problem	Language	Result	Execution time	Memory
132119		SirCeness	Two Antennas (JOI19_antennas)	C++14	22 / 100	750 ms	32128 KiB

antennas

#include <bits/stdc++.h>

using namespace std;
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define bas(x) #x << ": " << x << " "
#define prarr(x, n) cout << #x << ": "; for (int qsd = 0; qsd < n; qsd++) cout << x[qsd] << " "; cout << endl;
#define prarrv(x) cout << #x << ": "; for (int qsd = 0; qsd < (int)x.size(); qsd++) cout << x[qsd] << " "; cout << endl;
#define inside sl<=l&&r<=sr
#define outside sr<l||r<sl



typedef long long ll;
const ll INF = 1e9;

int n, q;
pair<ll, pair<int, int> > arr[200005];
list<pair<int, int> > events[200005];
ll stmin[800005];
ll stmax[800005];

void stcmax(int node, int l, int r){
	//cout << "stcmax(" << node << "," << l << ", " << r << ")"<< endl;
	if (l == r) stmax[node] = -INF;
	else {
		int m = (l+r)/2;
		stcmax(node*2, l, m);
		stcmax(node*2+1, m+1, r);
		stmax[node] = -INF;
	}
}

void stumax(int node, int l, int r, int ind, int val){
	if (l == r) stmax[node] = val;
	else {
		int m = (l+r)/2;
		if (ind <= m) stumax(node*2, l, m, ind, val);
		else stumax(node*2+1, m+1, r, ind, val);
		stmax[node] = max(stmax[node*2], stmax[node*2+1]);
	}
}

ll stqmax(int node, int l, int r, int sl, int sr){
	if (sl<=l&&r<=sr) return stmax[node];
	else if (sr<l||r<sl) return -INF;
	else {
		int m = (l+r)/2;
		return max(stqmax(node*2, l, m, sl, sr), stqmax(node*2+1, m+1, r, sl, sr));
	}
}


void stcmin(int node, int l, int r){
	if (l == r) stmin[node] = INF;
	else {
		int m = (l+r)/2;
		stcmin(node*2, l, m);
		stcmin(node*2+1, m+1, r);
		stmin[node] = INF;
	}
}

void stumin(int node, int l, int r, int ind, int val){
	if (l == r) stmin[node] = val;
	else {
		int m = (l+r)/2;
		if (ind <= m) stumin(node*2, l, m, ind, val);
		else stumin(node*2+1, m+1, r, ind, val);
		stmin[node] = min(stmin[node*2], stmin[node*2+1]);
	}
}

ll stqmin(int node, int l, int r, int sl, int sr){
	if (sl<=l&&r<=sr) return stmin[node];
	else if (sr<l||r<sl) return INF;
	else {
		int m = (l+r)/2;
		return min(stqmin(node*2, l, m, sl, sr), stqmin(node*2+1, m+1, r, sl, sr));
	}
}

int main(){
	cin >> n;
	for (int i = 0; i < n; i++){
		int w, a, b;
		cin >> w >> a >> b;
		arr[i] = mp(w, mp(a, b));
		events[max(0, i-b)].pb(mp(1, i));
		events[max(0, i-a+1)].pb(mp(-1, i));
	}
	
	ll ans = 0;
	
	stcmax(1, 0, n-1);
	stcmin(1, 0, n-1);
	//cout << "here" << endl;	
	
	for (int i = 0; i < n; i++){
		for (pair<int, int> eleman: events[i]){
			//cout << bas(eleman.first) << bas(eleman.second) << endl;
			if (eleman.first == 1){
				//cout << "set: " << eleman.second << endl;
				stumax(1, 0, n-1, eleman.second, arr[eleman.second].first);
				stumin(1, 0, n-1, eleman.second, arr[eleman.second].first);
			} else {
				//cout << "reset: " << i << endl;
				stumax(1, 0, n-1, eleman.second, -INF);
				stumin(1, 0, n-1, eleman.second, INF);
			}
		}
		//cout << "//islem\n";
		int rl = arr[i].second.first+i;
		int rr = arr[i].second.second+i;
		//cout << "query: " << rl << "," << rr << endl;
		//cout << bas(stqmax(1, 0, n-1, rl, rr)) << bas(stqmin(1, 0, n-1, rl, rr)) << endl;
		ans = max(ans, stqmax(1, 0, n-1, rl, rr) - arr[i].first);
		ans = max(ans, - stqmin(1, 0, n-1, rl, rr) + arr[i].first);
		//cout << bas(ans) << endl;
	}
	
	cout << ans << endl;
}

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