oj.uz

Submission #1046539

# Submission time Handle Problem Language Result Execution time Memory
1046539 2024-08-06T16:20:52 Z MrPavlito Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 118 ms 6212 KB 
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>

using namespace std;

const int MAXN = 1e5+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;
int n,q,k;

int seg[MAXN<<2];
int niz[MAXN];

void build(int nod, int l, int r)
{
    if(l==r)
    {
        seg[nod] = niz[l];
        return;
    }
    int mid = l+r >> 1;
    build(nod<<1, l, mid);
    build(nod<<1|1, mid+1, r);
    seg[nod] = seg[nod<<1] + seg[nod<<1|1];
}

void updatesingle(int nod, int l, int r,int index, int v)
{
    if(l == r)
    {
        seg[nod] = v;
        niz[index] = v;
        return;
    }
    int mid = l+r >> 1;
    if(index<=mid)updatesingle(nod<<1, l, mid, index, v);
    else updatesingle(nod<<1|1, mid+1, r, index, v);
    seg[nod] = seg[nod<<1] + seg[nod<<1|1];
}

void updaterange(int nod, int tl, int tr, int l, int r)
{
    if(tl> r || tr< l || tl>tr || seg[nod]==0)return;
    int mid = tl+tr>>1;
    if(tl>=l && tr<=r)
    {
        if(tl == tr)
        {
            seg[nod] /= k;
        }
        else if(seg[nod] > 0)
        {
            updaterange(nod<<1, tl, mid, l, r);
            updaterange(nod<<1|1, mid+1, tr, l, r);
            seg[nod] = seg[nod<<1] + seg[nod<<1|1];
        }
        return;
    }
    updaterange(nod<<1, tl, mid, l, r);
    updaterange(nod<<1|1, mid+1, tr, l, r);
    seg[nod] = seg[nod<<1] + seg[nod<<1|1];
}

int query(int nod, int tl, int tr, int l, int r)
{
    if(tl> r || tr< l || tl>tr || seg[nod]==0)return 0;
    if(tl>=l && tr<=r)return seg[nod];
    int mid = tl+tr >> 1;
    return query(nod<<1, tl, mid, l, r) + query(nod<<1|1, mid+1, tr, l, r);
}

signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--)
    {

        cin >> n >> q >> k;
        for(int i=1; i<=n; i++)cin >> niz[i];
        build(1,1,n);
        while(q--)
        {
            int a,b,c;
            cin >> a >> b >> c;
            if(a==1)updatesingle(1,1,n,b,c);
            else if(a==2 && k!=1)updaterange(1,1,n,b,c);
            else if(a==3)cout << query(1,1,n,b,c) << endl;
        }

    }
}

Compilation message

sterilizing.cpp: In function 'void build(long long int, long long int, long long int)':
sterilizing.cpp:28:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |     int mid = l+r >> 1;
      |               ~^~
sterilizing.cpp: In function 'void updatesingle(long long int, long long int, long long int, long long int, long long int)':
sterilizing.cpp:42:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |     int mid = l+r >> 1;
      |               ~^~
sterilizing.cpp: In function 'void updaterange(long long int, long long int, long long int, long long int, long long int)':
sterilizing.cpp:51:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     int mid = tl+tr>>1;
      |               ~~^~~
sterilizing.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int)':
sterilizing.cpp:75:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |     int mid = tl+tr >> 1;
      |               ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 2 ms 2396 KB Output is correct
12 Correct 2 ms 2396 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2908 KB Output is correct
2 Correct 21 ms 2908 KB Output is correct
3 Correct 19 ms 3448 KB Output is correct
4 Correct 24 ms 3448 KB Output is correct
5 Correct 29 ms 3672 KB Output is correct
6 Correct 30 ms 5968 KB Output is correct
7 Correct 30 ms 6212 KB Output is correct
8 Correct 29 ms 6128 KB Output is correct
9 Correct 30 ms 5972 KB Output is correct
10 Correct 32 ms 6012 KB Output is correct
11 Correct 28 ms 6036 KB Output is correct
12 Correct 28 ms 5968 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2396 KB Output is correct
2 Correct 5 ms 2652 KB Output is correct
3 Correct 7 ms 2652 KB Output is correct
4 Correct 22 ms 2648 KB Output is correct
5 Correct 25 ms 3160 KB Output is correct
6 Correct 28 ms 3164 KB Output is correct
7 Correct 25 ms 3404 KB Output is correct
8 Correct 25 ms 4712 KB Output is correct
9 Correct 24 ms 4444 KB Output is correct
10 Correct 24 ms 4444 KB Output is correct
11 Correct 23 ms 4440 KB Output is correct
12 Correct 27 ms 4444 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2652 KB Output is correct
2 Correct 42 ms 2800 KB Output is correct
3 Correct 49 ms 2652 KB Output is correct
4 Correct 54 ms 2852 KB Output is correct
5 Correct 62 ms 3548 KB Output is correct
6 Correct 69 ms 3416 KB Output is correct
7 Correct 59 ms 3412 KB Output is correct
8 Correct 84 ms 3416 KB Output is correct
9 Correct 72 ms 3412 KB Output is correct
10 Correct 83 ms 3548 KB Output is correct
11 Correct 61 ms 3420 KB Output is correct
12 Correct 118 ms 3408 KB Output is correct