CSES Pizzeria Queries
Difference between en2 and en3, changed 3 character(s)
Hi, I am on my adventure to solve CSES problem set. I found this nice editorial for Range Query section ↵
[here](https://mirror.codeforces.com/blog/entry/77128)↵
↵
But i guess some new problems were added or were skipped there. I am struggling in one such problem. [here](https://cses.fi/problemset/task/2206)↵
Any hint/approach will be highly appreciated!↵
↵
EDIT: Yay AC ! I tried to code it as simple as possible.↵
↵
<spoiler summary="AC solution">↵
↵
~~~~~↵
#include<iostream>↵
#include<map>↵
#include<vector>↵
#include<climits>↵
#include<queue>↵
#include<cmath>↵
#include<stack>↵
#include<string>↵
#include<algorithm>↵
#define pb push_back↵
#define N (lli)(1e6)↵
#define lli long long int↵
#define mod (lli)(1e9+7)↵
#define INF (11)↵
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)↵
#define pb push_back↵
using namespace std;↵
 ↵
void buildTree1(vector<lli>&arr,vector<lli>&tree,lli ns,lli ne,lli index)↵
{↵
    if(ns==ne)↵
    {↵
        tree[index] = arr[ns]+ns;↵
        return;↵
    }↵
    ↵
    lli mid = (ns+ne)/2;↵
    buildTree1(arr,tree,ns,mid,2*index);↵
    buildTree1(arr,tree,mid+1,ne,2*index+1);↵
    tree[index] = min(tree[2*index],tree[2*index+1]);↵
}↵
 ↵
void buildTree2(vector<lli>&arr,vector<lli>&tree,lli ns,lli ne,lli index)↵
{↵
    if(ns==ne)↵
    {↵
        tree[index] = arr[ns] - ns;↵
        return;↵
    }↵
    ↵
    lli mid = (ns+ne)/2;↵
    buildTree2(arr,tree,ns,mid,2*index);↵
    buildTree2(arr,tree,mid+1,ne,2*index+1);↵
    tree[index] = min(tree[2*index],tree[2*index+1]);↵
}↵
 ↵
void update1(vector<lli>&arr,vector<lli>&tree,lli ns,lli ne,lli toUpd,lli updVal,lli index)↵
{↵
    // no overlap↵
    if(ne<toUpd or  ns>toUpd) return;↵
    ↵
    // complete overlap↵
    if(ns==ne)↵
    {↵
        tree[index] = updVal + ns;↵
        return;↵
    }↵
    ↵
    // partial overlap↵
    lli mid = (ns+ne)/2;↵
    update1(arr, tree, ns, mid, toUpd, updVal, 2*index);↵
    update1(arr, tree, mid+1, ne, toUpd, updVal, 2*index+1);↵
    tree[index] = min(tree[2*index],tree[2*index+1]);↵
}↵
 ↵
void update2(vector<lli>&arr,vector<lli>&tree,lli ns,lli ne,lli toUpd,lli updVal,lli index)↵
{↵
    // no overlap↵
    if(ne<toUpd or  ns>toUpd) return;↵
    ↵
    // complete overlap↵
    if(ns==ne)↵
    {↵
        tree[index] = updVal - ns;↵
        return;↵
    }↵
    ↵
    // partial overlap↵
    lli mid = (ns+ne)/2;↵
    update2(arr, tree, ns, mid, toUpd, updVal, 2*index);↵
    update2(arr, tree, mid+1, ne, toUpd, updVal, 2*index+1);↵
    tree[index] = min(tree[2*index],tree[2*index+1]);↵
}↵
 ↵
 ↵
lli query(vector<lli>&arr,vector<lli>&tree,lli ns,lli ne,lli l ,lli r,lli index)↵
{↵
    // no overlap↵
    if(r<ns or l>ne) return LLONG_MAX;↵
    ↵
    ↵
    // complete overlap↵
    if(l<=ns and ne<=r) return tree[index];↵
    ↵
    // partial overlap↵
    lli mid = (ns+ne)/2;↵
    lli left = query(arr, tree, ns, mid, l, r, 2*index);↵
    lli right = query(arr,tree,mid+1,ne,l,r,2*index+1);↵
    return min(left,right);↵
}↵
 ↵
 ↵
int main()↵
{↵
    lli n,q;↵
    cin>>n>>q;↵
    vector<lli>arr(n);↵
    for(lli i=0;i<n;i++) cin>>arr[i];↵
    vector<lli>tree1(4*n+1);↵
    vector<lli>tree2(4*n+1);↵
    ↵
    buildTree1(arr, tree1, 0, n-1, 1);↵
    buildTree2(arr, tree2, 0, n-1, 1);↵
    ↵
    lli t,a,b;↵
    while(q--)↵
    {↵
        cin>>t;↵
        if(t==2)↵
        {↵
            cin>>a;↵
            lli left = query(arr, tree2, 0, n-1, 1, a-1, 1);↵
            lli right = query(arr,tree1,0,n-1,a-1,n-1,1);↵
            cout<<min(left+(a-1),right-(a-1))<<endl;↵
            ↵
        }↵
        else↵
        {↵
            cin>>a>>b;↵
            update1(arr, tree1, 0, n-1, a-1, b,1);↵
            update2(arr,tree2,0,n-1,a-1,b,1);↵
        }↵
    }↵
    ↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English kgargdun 2021-01-18 14:32:03 2 Tiny change: ', 0, n-1, 1, a-1, 1);' -> ', 0, n-1, 0, a-1, 1);'
en3 English kgargdun 2021-01-14 00:23:39 3 (published)
en2 English kgargdun 2021-01-13 20:41:16 3392 Tiny change: 'preciated!' -> 'preciated!\n\n\n<spoiler summary="AC solution">\n...\n</spoiler>' (saved to drafts)
en1 English kgargdun 2021-01-13 19:19:32 369 Initial revision (published)