oj.uz

Submission #132119

# Submission time Handle Problem Language Result Execution time Memory
132119 2019-07-18T10:20:08 Z SirCeness Two Antennas (JOI19_antennas) C++14
22 / 100
 750 ms 32128 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 27356 KB Output is correct
2 Correct 687 ms 29048 KB Output is correct
3 Correct 466 ms 27260 KB Output is correct
4 Correct 750 ms 31992 KB Output is correct
5 Correct 333 ms 18392 KB Output is correct
6 Correct 728 ms 31964 KB Output is correct
7 Correct 603 ms 29816 KB Output is correct
8 Correct 732 ms 32128 KB Output is correct
9 Correct 95 ms 9208 KB Output is correct
10 Correct 728 ms 31780 KB Output is correct
11 Correct 409 ms 21880 KB Output is correct
12 Correct 703 ms 31992 KB Output is correct
13 Correct 550 ms 31992 KB Output is correct
14 Correct 551 ms 31864 KB Output is correct
15 Correct 552 ms 31756 KB Output is correct
16 Correct 565 ms 32032 KB Output is correct
17 Correct 559 ms 31864 KB Output is correct
18 Correct 569 ms 31924 KB Output is correct
19 Correct 573 ms 31856 KB Output is correct
20 Correct 553 ms 31896 KB Output is correct
21 Correct 534 ms 31828 KB Output is correct
22 Correct 544 ms 31868 KB Output is correct
23 Correct 549 ms 31948 KB Output is correct
24 Correct 575 ms 31936 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4988 KB Output isn't correct
2 Halted 0 ms 0 KB -