oj.uz

Submission #994450

# Submission time Handle Problem Language Result Execution time Memory
994450 2024-06-07T16:20:13 Z De3b0o Weirdtree (RMI21_weirdtree) C++14
13 / 100
 107 ms 43032 KB 
#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*x)
#define rc (2*x+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 {-1,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++)
        se(1,1,n,i,h[i]);
}
void cut(int l, int r, int k)
{
    pll idx = mxg(1,1,n,l,r);
    if(idx.F>0)
        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);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 39 ms 17492 KB Output is correct
4 Correct 41 ms 17492 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 35924 KB Output is correct
2 Correct 105 ms 43032 KB Output is correct
3 Incorrect 23 ms 17244 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 39 ms 17492 KB Output is correct
4 Correct 41 ms 17492 KB Output is correct
5 Incorrect 1 ms 8540 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 39 ms 17492 KB Output is correct
4 Correct 41 ms 17492 KB Output is correct
5 Incorrect 1 ms 8540 KB Output isn't correct
6 Halted 0 ms 0 KB -