oj.uz

Submission #555940

# Submission time Handle Problem Language Result Execution time Memory
555940 2022-05-01T21:09:02 Z status_coding Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 245 ms 9484 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;

            if(k > 1)
                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 2 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 5 ms 596 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 5 ms 588 KB Output is correct
10 Correct 4 ms 588 KB Output is correct
11 Correct 4 ms 596 KB Output is correct
12 Correct 4 ms 468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 4268 KB Output is correct
2 Correct 46 ms 4444 KB Output is correct
3 Correct 43 ms 7076 KB Output is correct
4 Correct 59 ms 8888 KB Output is correct
5 Correct 69 ms 9428 KB Output is correct
6 Correct 75 ms 9484 KB Output is correct
7 Correct 66 ms 9420 KB Output is correct
8 Correct 71 ms 9436 KB Output is correct
9 Correct 60 ms 9292 KB Output is correct
10 Correct 61 ms 9380 KB Output is correct
11 Correct 65 ms 9260 KB Output is correct
12 Correct 75 ms 9260 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 852 KB Output is correct
2 Correct 19 ms 3252 KB Output is correct
3 Correct 21 ms 3260 KB Output is correct
4 Correct 58 ms 2032 KB Output is correct
5 Correct 83 ms 6728 KB Output is correct
6 Correct 76 ms 6752 KB Output is correct
7 Correct 55 ms 7216 KB Output is correct
8 Correct 77 ms 8000 KB Output is correct
9 Correct 76 ms 7872 KB Output is correct
10 Correct 85 ms 7908 KB Output is correct
11 Correct 74 ms 7868 KB Output is correct
12 Correct 81 ms 7880 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 3748 KB Output is correct
2 Correct 91 ms 3904 KB Output is correct
3 Correct 105 ms 3404 KB Output is correct
4 Correct 120 ms 2632 KB Output is correct
5 Correct 148 ms 6972 KB Output is correct
6 Correct 153 ms 6988 KB Output is correct
7 Correct 138 ms 6988 KB Output is correct
8 Correct 201 ms 6992 KB Output is correct
9 Correct 182 ms 7088 KB Output is correct
10 Correct 184 ms 6932 KB Output is correct
11 Correct 140 ms 6936 KB Output is correct
12 Correct 245 ms 7048 KB Output is correct