Submission #994445

#TimeUsernameProblemLanguageResultExecution timeMemory
994445De3b0oWeirdtree (RMI21_weirdtree)C++14
0 / 100
82 ms17708 KiB
#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) { pll idx = mxg(1,1,n,l,r); if(idx.F) se(1,1,n,idx.S,a[idx.S]-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); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...