oj.uz

Submission #952997

# Submission time Handle Problem Language Result Execution time Memory
952997 2024-03-25T09:53:20 Z ishat_jha Sterilizing Spray (JOI15_sterilizing) C++17
0 / 100
 5000 ms 5524 KB 
// 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--;
            build(0, n-1, 1, v, l, r, k);
        }
        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.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5019 ms 4720 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 677 ms 1400 KB Output is correct
2 Correct 1632 ms 3676 KB Output is correct
3 Correct 2604 ms 4372 KB Output is correct
4 Execution timed out 5024 ms 3468 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5097 ms 5524 KB Time limit exceeded
2 Halted 0 ms 0 KB -