| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1024935 | tolbi | Two Antennas (JOI19_antennas) | C++17 | 0 ms | 0 KiB |
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 tol(bi) (1LL<<((int)(bi)))
constexpr int MAXN = 200003;
constexpr ll INF = 1e15;
array<int,3> qu[MAXN];
array<int,3> arr[MAXN];
vector<pair<int,int>> rr[MAXN];
ll ansarr[MAXN];
struct SegTree{
ll tag1[MAXN*4],tag2[MAXN*4];
//tag1 subtree min
//tag2 subtree ans
//tag3 lazy
int tag3[MAXN*4], sz;
SegTree(int n):sz(tol(ceil(log2(n)+1))-1){
fill(tag1,tag1+sz,INF);
fill(tag2,tag2+sz,-INF);
fill(tag3,tag3+sz,0);
}
void dallan(int nd){
if (tag3[nd]){
tag2[nd]=max(tag2[nd],tag3[nd]-tag1[nd]);
if (nd*2+1<sz){
tag3[nd*2+1]=max(tag3[nd*2+1],tag3[nd]);
tag3[nd*2+2]=max(tag3[nd*2+2],tag3[nd]);
}
tag3[nd]=0;
}
}
void upd1(int nd, ll val){
int l = 0, r = sz/2;
int node = 0;
while (l<r){
dallan(node);
int mid = l+(r-l)/2;
if (mid>=nd){
r=mid;
node=node*2+1;
}
else {
l=mid+1;
node=node*2+2;
}
}
dallan(node);
tag1[node]=val;
while (node){
node=(node-1)/2;
tag1[node]=min(tag1[node*2+1],tag1[node*2+2]);
}
}
void upd2(int tl, int tr, int val, int l = 0, int r = -1, int node = 0){
dallan(node);
if (r==-1) r = sz/2;
if (l>=tl && r<=tr) {
tag3[node]=max(tag3[node],val);
dallan(node);
return;
}
if (l>tr || r<tl) return;
int mid = l+(r-l)/2;
if (mid>=tl) upd2(tl, tr, val, l, mid, node*2+1);
else dallan(node*2+1);
if (mid<tr) upd2(tl, tr, val, mid+1, r, node*2+2);
else dallan(node*2+2);
tag2[node]=max(tag2[node*2+1],tag2[node*2+2]);
}
ll query(int tl, int tr, int l = 0, int r = -1, int node = 0){
if (r==-1) r = sz/2;
dallan(node);
if (l>=tl && r<=tr) return tag2[node];
if (l>tr || r<tl) return -INF;
int mid = l+(r-l)/2;
ll ret = -INF;
if (mid>=tl) ret=max(ret,query(tl,tr,l,mid,node*2+1));
if (mid<tr) ret=max(ret,query(tl,tr,mid+1,r,node*2+2));
return ret;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
memset(ansarr,-1,sizeof(ansarr));
int n;cin>>n;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < 3; ++j){
cin>>arr[i][j];
}
}
int q;cin>>q;
for (int i = 0; i < q; ++i)
{
cin>>qu[i][0]>>qu[i][1];
qu[i][0]--,qu[i][1]--;
qu[i][2]=i;
}
function<void(void)> solve = [&](void)->void{
for (int i = 0; i < n-1; ++i)
{
if (i+arr[i][1]>=n) continue;
rr[min(n-1,i+arr[i][1])].push_back({i,1});
rr[min(n,i+arr[i][2]+1)].push_back({i,-1});
}
sort(qu,qu+q,[&](const array<int,3> &a, const array<int,3> &b){
return a[1]<b[1];
});
SegTree segtree(n);
int ind = 0;
for (int i = 0; i < n; i++){
while (rr[i].size()){
int node = rr[i].back().first;
int flag = rr[i].back().second;
rr[i].pop_back();
if (flag==1){
segtree.upd1(node,arr[node][0]);
}
else {
segtree.upd1(node,INF);
}
}
segtree.upd2(i-arr[i][2],i-arr[i][1],arr[i][0]);
while (ind<q && qu[ind][1]==i){
ansarr[qu[ind][2]]=max(ansarr[qu[ind][2]],segtree.query(qu[ind][0],qu[ind][1]));
ind++;
}
}
};
solve();
reverse(arr, arr+n);
for (int i = 0; i < q; ++i)
{
qu[i][0]=n-qu[i][0]-1;
qu[i][1]=n-qu[i][1]-1;
swap(qu[i][0],qu[i][1]);
}
solve();
for (int i = 0; i < q; ++i)
{
cout<<ansarr[i]<<endl;
}
}