oj.uz

Submission #1046535

# Submission time Handle Problem Language Result Execution time Memory
1046535 2024-08-06T16:18:57 Z MrPavlito Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 3668 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)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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 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 3 ms 2396 KB Output is correct
10 Correct 2 ms 2548 KB Output is correct
11 Correct 2 ms 2392 KB Output is correct
12 Correct 2 ms 2392 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2561 ms 2936 KB Output is correct
2 Correct 1581 ms 3020 KB Output is correct
3 Correct 2614 ms 3372 KB Output is correct
4 Correct 4275 ms 3416 KB Output is correct
5 Execution timed out 5075 ms 3668 KB Time limit exceeded
6 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 6 ms 2692 KB Output is correct
3 Correct 7 ms 2652 KB Output is correct
4 Correct 20 ms 2744 KB Output is correct
5 Correct 28 ms 3320 KB Output is correct
6 Correct 25 ms 3352 KB Output is correct
7 Execution timed out 5048 ms 3292 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2648 KB Output is correct
2 Correct 43 ms 2808 KB Output is correct
3 Correct 49 ms 2752 KB Output is correct
4 Correct 55 ms 2900 KB Output is correct
5 Correct 62 ms 3344 KB Output is correct
6 Correct 70 ms 3408 KB Output is correct
7 Correct 59 ms 3408 KB Output is correct
8 Correct 91 ms 3408 KB Output is correct
9 Correct 74 ms 3416 KB Output is correct
10 Correct 93 ms 3408 KB Output is correct
11 Correct 63 ms 3564 KB Output is correct
12 Correct 111 ms 3548 KB Output is correct