This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
//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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |