Submission #953038

#	Time	Username	Problem	Language	Result	Execution time	Memory
953038		ishat_jha	Sterilizing Spray (JOI15_sterilizing)	C++14	0 / 100	73 ms	4780 KiB

sterilizing

// Author - Ishat Kumar Jha
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ff first
#define ss second

vector<ll> seg;

void build(ll start, ll end, ll index, vector<ll> &arr, ll l, ll r, ll k)
{
    if(start == end && l <= start && start <= r)
    {
        arr[start] = (arr[start] / k);
        seg[index] = arr[start];
        return;
    }
    else if(start == end)
    {
        return;
    }
    ll mid = (start + end)/2;
    ll left = 2 * index;
    ll right = (2 * index) + 1;
    build(start, mid, left, arr, l, r, k);
    build(mid+1, end, right, arr, l, r, k);
    seg[index] = (seg[left] + seg[right]);
}

void update(ll start, ll end, ll index, vector<ll> &arr, ll pos, ll val)
{
    if(start == end)
    {
        seg[index] = val;
        arr[start] = val;
        return;
    }
    ll mid = (start + end)/2;
    ll left = 2 * index;
    ll right = (2 * index) + 1;
    if(mid >= pos)
    {
        update(start, mid, left, arr, pos, val);
    }
    else
    {
        update(mid+1, end, right, arr, pos, val);
    }
    seg[index] = seg[left] + seg[right];
}

int query(ll start, ll end, ll index, ll l, ll r)
{
    // l <= start <= end <= r
    if(l <= start && end <= r)
    {
        return seg[index];
    }
    if(start > r || l > end)
    {
        return 0;
    }
    ll mid = (start + end)/2;
    ll left = (2 * index);
    ll right = (2 * index) + 1;
    ll kk = query(start, mid, left, l, r);
    ll qq = query(mid+1, end, right, l, r);
    return kk + qq;
}

void solvr()
{
    ll n, q, k;
    cin >> n >> q >> k;
    vector<ll> v(n);
    seg.resize(8 * n);
    for(ll i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    build(0, n-1, 1, v, 0, n-1, 1);
    for(ll i = 0; i < q; i++)
    {
        ll code;
        cin >> code;
        if(code == 1)
        {
            ll pos, val;
            cin >> pos >> val;
            pos--;
            update(0, n-1, 1, v, pos, val);
            //cout << v[pos] << " 1" << endl;
        }
        else if(code == 2)
        {
            ll l, r;
            cin >> l >> r;
            l--;
            r--;
        }
        else if(code == 3)
        {
            ll l, r;
            cin >> l >> r;
            l--;
            r--;
            cout << query(0, n-1, 1, l, r) << endl;
        }
    }
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	long long int t = 1;
	//cin >> t;
	while(t--)
	{
		solvr();
	}
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75