Submission #994444

#	Time	Username	Problem	Language	Result	Execution time	Memory
994444		De3b0o	Weirdtree (RMI21_weirdtree)	C++14	0 / 100	79 ms	24724 KiB

weirdtree

#include "weirdtree.h"
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define ppb pop_back()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "Yes" << "\n";
#define no cout << "No" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define sqr 340
#define mod 1000000007
#define mid ((l+r)/2)
#define lc (2*n)
#define rc (2*n+1)

using namespace std;

ll n ,q;
ll a[300009] , mx[2000009] , sum[2000009] , mxidx[2000009];

void se(ll x , ll l , ll r , ll idx , ll val)
{
    if(l>idx||r<idx)
        return;
    if(l==r)
    {
        mx[x]=val;
        sum[x]=val;
        mxidx[x]=idx;
        a[idx]=val;
        return;
    }
    se(lc,l,mid,idx,val);
    se(rc,mid+1,r,idx,val);
    sum[x]=sum[lc]+sum[rc];
    if(mx[rc]>mx[lc])
        mxidx[x]=mxidx[rc];
    else
        mxidx[x]=mxidx[lc];
    mx[x]=max(mx[lc],mx[rc]);
}

ll sumg(ll x , ll l , ll r , ll l1 , ll r1)
{
    if(l>r1||r<l1)
        return 0;
    if(l>=l1&&r<=r1)
        return sum[x];
    return sumg(lc,l,mid,l1,r1)+sumg(rc,mid+1,r,l1,r1);
}

pll mxg(ll x , ll l , ll r , ll l1 , ll r1)
{
    if(l>r1||r<l1)
        return {0,0};
    if(l>=l1&&r<=r1)
        return {mx[x],mxidx[x]};
    pll mx1 = mxg(lc,l,mid,l1,r1);
    pll mx2 = mxg(rc,mid+1,r,l1,r1);
    if(mx2.F>mx1.F)
        return mx2;
    else
        return mx1;
}

void initialise(int N, int Q, int h[])
{
    n=N;
    q=Q;
    for(int i = 1 ; n>=i ; i++)
    {
        a[i]=h[i];
        se(1,1,n,i,a[i]);
    }
}
void cut(int l, int r, int k)
{
    ll idx = mxg(1,1,n,l,r).S;
    se(1,1,n,idx,a[idx]-1);
}
void magic(int i, int x)
{
    se(1,1,n,i,x);
}
long long int inspect(int l, int r)
{
    return sumg(1,1,n,l,r);
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 19
• Subtask 5: 0 / 10
• Subtask 6: 0 / 21
• Subtask 7: 0 / 29