oj.uz

Submission #555937

# Submission time Handle Problem Language Result Execution time Memory
555937 2022-05-01T21:07:02 Z status_coding Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 9404 KB 
#include <bits/stdc++.h>

using namespace std;

struct segS
{
    long long sum, maxi;
};

long long n,k,q;
vector<segS> seg;

void upd(int i, int st, int dr, int p, long long val)
{
    if(st == dr)
    {
        seg[p].sum = seg[p].maxi = val;
        return;
    }

    int mij =  (st+dr)/2;

    if(i <= mij)
        upd(i, st, mij, 2*p, val);
    else
        upd(i, mij+1, dr, 2*p+1, val);

    seg[p].sum = seg[2*p].sum + seg[2*p+1].sum;
    seg[p].maxi = max(seg[2*p].maxi, seg[2*p+1].maxi);
}

void imp(int stt, int drt, int st, int dr, int p)
{
    if(st == dr)
    {
        seg[p].sum /= k;
        seg[p].maxi /= k;
        return;
    }

    int mij = (st+dr)/2;

    if(stt <= st && dr <= drt)
    {
        if(seg[2*p].maxi > 0)
            imp(stt, drt, st, mij, 2*p);

        if(seg[2*p+1].maxi > 0)
            imp(stt, drt, mij+1, dr, 2*p+1);
    }
    else
    {
        if(drt <= mij)
            imp(stt, drt, st, mij, 2*p);
        else if(stt > mij)
            imp(stt, drt, mij+1, dr, 2*p+1);
        else
        {
            imp(stt, mij, st, mij, 2*p);
            imp(mij+1, drt, mij+1, dr, 2*p+1);
        }
    }

    seg[p].sum = seg[2*p].sum + seg[2*p+1].sum;
    seg[p].maxi = max(seg[2*p].maxi, seg[2*p+1].maxi);
}

long long query(int stt, int drt, int st, int dr, int p)
{
    if(stt == st && drt == dr)
        return seg[p].sum;

    int mij = (st+dr)/2;

    if(drt <= mij)
        return query(stt, drt, st, mij, 2*p);
    else if(stt > mij)
        return query(stt, drt, mij+1, dr, 2*p+1);
    else
        return query(stt, mij, st, mij, 2*p) + query(mij+1, drt, mij+1, dr, 2*p+1);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>q>>k;
    seg.resize(4*n+4);

    for(int i=1;i<=n;i++)
    {
       long long x;
       cin>>x;

       upd(i, 1, n, 1, x);
    }

    while(q)
    {
        q--;

        int tip;
        cin>>tip;

        if(tip == 1)
        {
            long long i, val;
            cin>>i>>val;

            upd(i, 1, n, 1, val);
        }

        if(tip == 2)
        {
            int l, r;
            cin>>l>>r;

            imp(l, r, 1, n, 1);
        }

        if(tip == 3)
        {
            int l, r;
            cin>>l>>r;

            cout<<query(l, r, 1, n, 1)<<'\n';
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 5 ms 592 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 5 ms 588 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 7 ms 592 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 4 ms 596 KB Output is correct
12 Correct 4 ms 588 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1108 KB Output is correct
2 Correct 18 ms 3372 KB Output is correct
3 Correct 24 ms 3508 KB Output is correct
4 Correct 62 ms 3008 KB Output is correct
5 Correct 86 ms 8004 KB Output is correct
6 Correct 78 ms 7984 KB Output is correct
7 Execution timed out 5067 ms 7620 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 5188 KB Output is correct
2 Correct 99 ms 5376 KB Output is correct
3 Correct 111 ms 4308 KB Output is correct
4 Correct 113 ms 4248 KB Output is correct
5 Correct 173 ms 9304 KB Output is correct
6 Correct 155 ms 9404 KB Output is correct
7 Correct 139 ms 9376 KB Output is correct
8 Correct 200 ms 9388 KB Output is correct
9 Correct 160 ms 9108 KB Output is correct
10 Correct 179 ms 9116 KB Output is correct
11 Correct 161 ms 9164 KB Output is correct
12 Correct 234 ms 9132 KB Output is correct