oj.uz

Submission #1046538

# Submission time Handle Problem Language Result Execution time Memory
1046538 2024-08-06T16:20:11 Z MrPavlito Sterilizing Spray (JOI15_sterilizing) C++17
75 / 100
 111 ms 3672 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 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
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2392 KB Output is correct
2 Correct 5 ms 2652 KB Output is correct
3 Correct 7 ms 2652 KB Output is correct
4 Correct 19 ms 2732 KB Output is correct
5 Correct 27 ms 3160 KB Output is correct
6 Correct 26 ms 3164 KB Output is correct
7 Incorrect 38 ms 3672 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2652 KB Output is correct
2 Correct 42 ms 2808 KB Output is correct
3 Correct 49 ms 2648 KB Output is correct
4 Correct 54 ms 2900 KB Output is correct
5 Correct 60 ms 3408 KB Output is correct
6 Correct 72 ms 3416 KB Output is correct
7 Correct 58 ms 3412 KB Output is correct
8 Correct 84 ms 3408 KB Output is correct
9 Correct 73 ms 3544 KB Output is correct
10 Correct 83 ms 3588 KB Output is correct
11 Correct 61 ms 3420 KB Output is correct
12 Correct 111 ms 3412 KB Output is correct