Submission #951610

#TimeUsernameProblemLanguageResultExecution timeMemory
951610hengliaoTwo Antennas (JOI19_antennas)C++14
Compilation error
0 ms0 KiB
#include<bits/stdc++.h> using namespace std; #define F first #define S second #define pb push_back #define vll vector<ll> #define pll pair<ll, ll> typedef long long ll; const ll mxN=2e5+5; const ll inf=1e18; ll h[mxN]; ll a[mxN]; ll b[mxN]; ll n, q; vll add[mxN]; vll minu[mxN]; struct segtree{ vll tree; ll treelen; void init(ll siz){ treelen=siz+1; while(__builtin_popcountll(treelen)!=1){ treelen++; } tree=vll(2*treelen, 0); } void update(ll idx, ll val){ ll tar=treelen+idx; tree[tar]=val; tar/=2; while(tar>0){ tree[tar]=max(tree[2*tar], tree[2*tar+1]); tar/=2; } } ll getmax(ll idx, ll low, ll high, ll qlow, ll qhigh){ if(low>=qlow && high<=qhigh){ return tree[idx]; } if(low>qhigh || high<qlow){ return 0; } ll mid=(low+high)/2; return max(getmax(2*idx, low, mid, qlow, qhigh), getmax(2*idx+1, mid+1, high, qlow, qhigh)); } }; struct segtree2{ vll tree; ll treelen; void init(ll siz){ treelen=siz+1; while(__builtin_popcountll(treelen)!=1){ treelen++; } tree=vll(2*treelen, inf); } void update(ll idx, ll val){ ll tar=treelen+idx; tree[tar]=val; tar/=2; while(tar>0){ tree[tar]=min(tree[2*tar], tree[2*tar+1]); tar/=2; } } ll getmin(ll idx, ll low, ll high, ll qlow, ll qhigh){ if(low>=qlow && high<=qhigh){ return tree[idx]; } if(low>qhigh || high<qlow){ return inf; } ll mid=(low+high)/2; return min(getmin(2*idx, low, mid, qlow, qhigh), getmin(2*idx+1, mid+1, high, qlow, qhigh)); } }; segtree seg1; segtree2 seg2; ll solve2(ll l, ll r){ seg1=vll(2*seg.treelen, 0); seg2=vll(2*seg.treelen, inf); /*for(auto it:seg2.tree){ cout<<it<<' '; } cout<<'\n';*/ for(ll i=l;i<=r;i++){ add[i].clear(); minu[i].clear(); } ll re=-1; for(ll i=l;i<=r;i++){ for(auto it:add[i]){ seg1.update(it, h[it]); seg2.update(it, h[it]); } for(auto it:minu[i]){ seg1.update(it, 0); seg2.update(it, inf); } if(i+a[i]<=r){ add[i+a[i]].pb(i); } if(i+b[i]+1<=r){ minu[i+b[i]+1].pb(i); } ll low=i-b[i], high=i-a[i]; low=max(low, l); //cout<<i<<' '<<low<<' '<<high<<'\n'; if(high<low) continue; ll mn=seg2.getmin(1, 0, seg2.treelen-1, low, high); //cout<<mn<<'\n'; if(mn!=inf){ re=max(re, abs(h[i]-mn)); } ll mx=seg1.getmax(1, 0, seg1.treelen-1, low, high); //cout<<mx<<'\n'; if(mx!=0){ re=max(re, abs(h[i]-mx)); } } return re; } void solve(){ cin>>n; for(ll i=0;i<n;i++){ cin>>h[i]>>a[i]>>b[i]; } cin>>q; for(ll i=0;i<q;i++){ ll l, r; cin>>l>>r; l--; r--; cout<<solve2(l, r); if(i<q-1) cout<<'\n'; } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }

Compilation message (stderr)

antennas.cpp: In function 'll solve2(ll, ll)':
antennas.cpp:95:16: error: 'seg' was not declared in this scope; did you mean 'seg2'?
   95 |     seg1=vll(2*seg.treelen, 0);
      |                ^~~
      |                seg2