PROBLEM LINK:
Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest
Author: Ashish Vishal, Aditya Kumar Singh
Tester: Shikhar Sharma, Daanish Mahajan
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Data structures
PROBLEM:
Given an array of N stones each of some height.
For each query, we are given two positions and we have to output the total
number of stones visible from both positions.
EXPLANATION:
While maintaining a stack we can easily determine the number of stones
visible from each position in linear time.
Thereafter we can calculate the height and position of the maximum stone
present between stones A and B.
It is not tough to see that the number of stones visible from this position
is also the number of stones that are visible from both positions A and B.
As for the implementation details we can use a segment Tree to determine the
maximum between A and B.
Also we maintain a map where for each height we store a pair of position
and size of stack (which corresponds to the number of visible stones from this position).
Finally we can just use lower_bound to find out the exact position of the maximum.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define is insert
#define rep1(i,a,b) for(long long i=a;i<=b;i++)
#define F first
#define S second
#define file ifstream fin(“input.txt”);ofstream fout(“output.txt”);
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fr(n) for(long long i=0;i<n;i++)
#define rep(i,a,b) for(long long i=a;i<b;i++)
#define ALL(x) (x).begin(), (x).end()
typedef long long int ll;
typedef long double ld;
typedef vector vi;
ll n,m,l,r,siz;
vi h,tree,sgr;
void build_segtree()
{
tree.resize(2*siz,0);
rep(i,siz,2*siz)
tree[i]=i-siz+1;
for(int i=siz-1;i>0;i--)
{
if(h[tree[2*i]]>h[tree[2*i+1]])
tree[i]=tree[2*i];
else
tree[i]=tree[2*i+1];
}
}
ll query(ll node,ll l,ll r,ll x,ll y)
{
if(l>r || y<l || x>r)
return 0;
if(x<=l && r<=y)
return tree[node];
ll id1=query(2*node,l,(l+r)/2,x,y);
ll id2=query(2*node+1,1+(l+r)/2,r,x,y);
if(h[id1]>h[id2])
return id1;
else
return id2;
}
void right_next_gr()
{
sgr.resize(n+1,0);
stack<ll>st;
for(int i=n;i>0;i--)
{
while(!st.empty()&&h[i]>=h[st.top()])
st.pop();
if(!st.empty())
sgr[i]=1+sgr[st.top()];
st.push(i);
}
}
void solve()
{
cin>>n>>m;
siz=pow(2,ceil(log2(n)));
h.clear();
tree.clear();
sgr.clear();
h.resize(siz+1,0);
rep(i,1,n+1)cin>>h[i];
build_segtree();
right_next_gr();
fr(m)
{
cin>>l>>r;
if(l>r)
swap(l,r);
ll ind=query(1,1,siz,l,r);
cout<<sgr[ind]<<"\n";
}
}
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("inputf.in", "r", stdin);
freopen("outputf.in", "w", stdout);
#endif
fast;
ll t=1;
cin>>t;
while(t--)
solve();
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#define FAST std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define F first
#define S second
#define mp make_pair
////-------------------------------------------------------------------------
#define int long long ////////////
////--------------------------------------------------------------------------
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define sz(s) (int)((s).size())
#define rep(i,a,n) for(int i=a ; i<n ; i++)
#define nl "\n"
const int N = 2e5+5;
void construct_segment_tree(vector<int>& segtree, vector<int>& a, int n)
{
for (int i = 0; i < n; i++)
segtree[n + i] = a[i];
for (int i = n - 1; i >= 1; i--)
segtree[i] = max(segtree[2 * i],
segtree[2 * i + 1]);
}
void update(vector<int>& segtree, int pos, int value, int n)
{
pos += n;
segtree[pos] = value;
while (pos > 1) {
pos >>= 1;
segtree[pos] = max(segtree[2 * pos],
segtree[2 * pos + 1]);
}
}
int range_query(vector<int>& segtree, int left, int right, int n)
{
left += n;
right += n;
int ma = INT_MIN;
while (left < right) {
if (left & 1) {
ma = max(ma, segtree[left]);
left++;
}
if (right & 1) {
right--;
ma = max(ma, segtree[right]);
}
left /= 2;
right /= 2;
}
return ma;
}
//-------------------------------------------------------------------------------
void do2win(int test)
{
int n,m; cin>>n>>m;
vi h(n);
rep(i,0,n) cin>>h[i];
vi segtree(2*n);
construct_segment_tree(segtree,h,n);
map< int, set<pii> > M;
stack<int> st;
for(int i=n-1;i>=0;i--)
{
while((!st.empty())&&(st.top()<=h[i]))
st.pop();
st.push(h[i]);
M[h[i]].insert(mp(i,sz(st)));
}
while(m--)
{
int k,l; cin>>k>>l; k--,l--;
if(k>l) swap(k,l);
int mx=range_query(segtree,k,l+1,n);
auto it=M[mx].lower_bound(mp(k,0));
pii p=*it;
int ans=p.S-1;
cout<<ans<<nl;
}
}
//-------------------------------------------------------------------------------
signed main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt","w", stderr);
#endif
///+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
FAST;
cout<<fixed<<setprecision(20);
///+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
int test; test=1;
cin>>test;
for(int i=1;i<=test;i++)
{
do2win(i);
}
return 0;
}