#define ll long long
#define ull unsigned ll
#define pii pair<int, int>
#define ppii pair<pii, int>
#include <bits/stdc++.h>
using namespace std;
int left(int i)
{
return 2*i;
}
int right(int i)
{
return 2*i+1;
}
int par(int i)
{
return i/2;
}
ll query(vector<ll>& s, int a, int b, int l, int r, int i)
{
//cout<<"HERE: "<<i<<" => <<endl;
if(l <= a && b <= r)
{
//cout<<"END"<<endl;
return s[i];
}
if(r < a || b < l)
{
//cout<<"END"<<endl;
return numeric_limits<ll>::min();
}
int m = (a+b)/2;
return max(query(s, a, m, l, r, left(i)), query(s, m+1, b, l, r, right(i)));
}
void propagate(vector<ll>& s, int i)
{
s[i] = max(s[left(i)], s[right(i)]);
if(i > 1)
{
propagate(s, par(i));
}
}
void update(vector<ll>& s, int i, ll v)
{
s[i+(s.size()/2)] = v;
propagate(s, par(i+(s.size()/2)));
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin>>n;
vector<ll> h(n); //heights
vector<pii> a(n); //Bereiche
for(int i = 0; i < n; i++)
{
cin>>h[i]>>a[i].first>>a[i].second;
}
int segnodes = 2*pow(2, ceil(log2(n)));
//Segtrees for max:
vector<ll> s(segnodes, numeric_limits<ll>::min()); //positive heights
vector<ll> ns(segnodes, numeric_limits<ll>::min()); //negative heights
int q;
cin>>q;
vector<ppii> requests(q);
for(int i = 0; i < q; i++)
{
int l, r;
cin>>l>>r;
requests[i] = {{l, r}, i};
}
sort(requests.begin(), requests.end());
vector<ll> result(q);
int qindex = 0;
while(qindex < q)
{
if(requests[qindex].first.first == requests[qindex].first.second)
{
result[requests[qindex].second] = -1;
qindex++;
}
else
{
int l = requests[qindex].first.first;
ll output = -1;
priority_queue<pii, vector<pii>, greater<pii>> st; //starts: distance, index
priority_queue<pii, vector<pii>, greater<pii>> g; //goals: distance, index
st.push({a[l-1].first+l, l});
g.push({a[l-1].second+l+1, l});
//cout<<"___________________________________NEW QUERY!!!"<<endl;
int j = l+1;
while(qindex < q && requests[qindex].first.first == l)
{
int r = requests[qindex].first.second;
//cout<<"-------->: "<<j<<endl;
while(!st.empty() && st.top().first == j)
{
update(s, st.top().second-1, h[st.top().second-1]);
update(ns, st.top().second-1, 0-h[st.top().second-1]);
//cout<<"TAKE "<<st.top().second<<endl;
st.pop();
}
while(!g.empty() && g.top().first == j)
{
update(s, g.top().second-1, numeric_limits<ll>::min());
update(ns, g.top().second-1, numeric_limits<ll>::min());
//cout<<"DROP "<<g.top().second<<endl;
g.pop();
}
st.push({a[j-1].first+j, j});
g.push({a[j-1].second+j+1, j});
/*cout<<"SEGTREE S: "<<endl;
for(ll y : s)
{
cout<<y<<" ";
}
cout<<endl;*/
int left = max(j-a[j-1].second, l);
int right = max(j-a[j-1].first, l);
//cout<<"LEFT: "<<left<<", RIGHT: "<<right<<endl;
ll biggest = query(s, 1, segnodes/2, left, right, 1);
ll smallest = query(ns, 1, segnodes/2, left, right, 1);
//cout<<"BIGGEST: "<<biggest<<", SMALLEST: "<<smallest<<endl;
if(biggest > numeric_limits<ll>::min())
{
//cout<<"HEREBIG"<<endl;
output = max(output, abs(h[j-1]-biggest));
}
if(smallest > numeric_limits<ll>::min())
{
//cout<<"HERESMALL"<<endl;
output = max(output, abs(h[j-1]+smallest));
}
//cout<<"OUTPUT: "<<output<<endl;
if(j == r)
{
while(qindex < q && requests[qindex].first.second == r)
{
result[requests[qindex].second] = output;
qindex++;
}
}
j++;
}
s.assign(segnodes, numeric_limits<ll>::min());
ns.assign(segnodes, numeric_limits<ll>::min()); }
}
for(ll i : result)
{
cout<<i<<"\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
177 ms |
14252 KB |
Output is correct |
| 2 |
Correct |
265 ms |
14568 KB |
Output is correct |
| 3 |
Correct |
129 ms |
12644 KB |
Output is correct |
| 4 |
Correct |
205 ms |
14560 KB |
Output is correct |
| 5 |
Correct |
79 ms |
7448 KB |
Output is correct |
| 6 |
Correct |
230 ms |
14700 KB |
Output is correct |
| 7 |
Correct |
171 ms |
13120 KB |
Output is correct |
| 8 |
Correct |
193 ms |
14564 KB |
Output is correct |
| 9 |
Correct |
28 ms |
2260 KB |
Output is correct |
| 10 |
Correct |
246 ms |
14564 KB |
Output is correct |
| 11 |
Correct |
124 ms |
7996 KB |
Output is correct |
| 12 |
Correct |
207 ms |
14628 KB |
Output is correct |
| 13 |
Correct |
170 ms |
14692 KB |
Output is correct |
| 14 |
Correct |
164 ms |
14704 KB |
Output is correct |
| 15 |
Correct |
151 ms |
13800 KB |
Output is correct |
| 16 |
Correct |
159 ms |
13544 KB |
Output is correct |
| 17 |
Correct |
172 ms |
14648 KB |
Output is correct |
| 18 |
Correct |
151 ms |
13496 KB |
Output is correct |
| 19 |
Correct |
162 ms |
14704 KB |
Output is correct |
| 20 |
Correct |
159 ms |
14700 KB |
Output is correct |
| 21 |
Correct |
175 ms |
14608 KB |
Output is correct |
| 22 |
Correct |
152 ms |
14600 KB |
Output is correct |
| 23 |
Correct |
164 ms |
13528 KB |
Output is correct |
| 24 |
Correct |
174 ms |
13624 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
