oj.uz

Submission #292940

# Submission time Handle Problem Language Result Execution time Memory
292940 2020-09-07T14:54:11 Z davooddkareshki Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 320 ms 8188 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair

typedef long long ll;

const int maxn = 1e5+10;
const int mod = 1e9+7;
const ll inf = 1e9+10;

int n, m, k, q;
int a[maxn];
int sum[maxn<<2], mx[maxn<<2];

void build(int v = 1, int tl = 1, int tr = n)
{
    if(tl == tr)
    {
        mx[v] = sum[v] = a[tl];
        return;
    }

    int tm = (tl + tr) >> 1;
    build(v<<1, tl, tm);
    build(v<<1|1, tm+1, tr);
    mx[v] = max(mx[v<<1], mx[v<<1|1]);
    sum[v] = sum[v<<1] + sum[v<<1|1];
}

void DO(int l, int r, int v = 1, int tl = 1, int tr = n)
{
    if(mx[v] == 0 || l > r || k == 1) return;
    if(tl == tr)
    {
        mx[v] /= k;
        sum[v] /= k;
        return;
    }

    int tm = (tl + tr) >> 1;
    DO(l, min(tm,r), v<<1, tl, tm);
    DO(max(tm+1,l), r, v<<1|1, tm+1, tr);
    mx[v] = max(mx[v<<1], mx[v<<1|1]);
    sum[v] = sum[v<<1] + sum[v<<1|1];
}

void _set(int pos, int val, int v = 1, int tl = 1, int tr = n)
{
    if(tl == tr)
    {
        mx[v] = sum[v] = val;
        return;
    }

    int tm = (tl + tr) >> 1;
    if(pos <= tm) _set(pos, val, v<<1, tl, tm);
    else          _set(pos, val, v<<1|1, tm+1, tr);
    mx[v] = max(mx[v<<1], mx[v<<1|1]);
    sum[v] = sum[v<<1] + sum[v<<1|1];
}

int sum_qu(int l, int r, int v = 1, int tl = 1, int tr = n)
{
    if(l > r) return 0;
    if(tl == l && tr == r) return sum[v];

    int tm = (tl + tr) >> 1;
    return sum_qu(l, min(tm,r), v<<1, tl, tm) +
            sum_qu(max(tm+1,l), r, v<<1|1, tm+1, tr);
}

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

    cin>> n >> q >> k;
    for(int i = 1; i <= n; i++) cin>> a[i];
    build();

    while(q--)
    {
        int tp; cin>> tp;
        if(tp == 1)
        {
            int pos, val; cin>> pos >> val;
            _set(pos,val);
        }
        if(tp == 2)
        {
            int l, r; cin>> l >> r;
            DO(l,r);
        }
        if(tp == 3)
        {
            int l, r; cin>> l >> r;
            cout<< sum_qu(l,r) <<"\n";
        }
    }
}
/*
5 10 3
1 2 8 1 3
1 2 5
2 3 5
3 2 5
2 1 4
1 3 2
3 3 5
1 2 4
2 1 2
1 1 4
3 1 5
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 5124 KB Output is correct
2 Correct 47 ms 4728 KB Output is correct
3 Correct 44 ms 7032 KB Output is correct
4 Correct 59 ms 7800 KB Output is correct
5 Correct 67 ms 8188 KB Output is correct
6 Correct 68 ms 8144 KB Output is correct
7 Correct 69 ms 8148 KB Output is correct
8 Correct 68 ms 8184 KB Output is correct
9 Correct 63 ms 8008 KB Output is correct
10 Correct 65 ms 8056 KB Output is correct
11 Correct 64 ms 8056 KB Output is correct
12 Correct 64 ms 8056 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1152 KB Output is correct
2 Correct 14 ms 3072 KB Output is correct
3 Correct 18 ms 3200 KB Output is correct
4 Correct 51 ms 2808 KB Output is correct
5 Correct 69 ms 6776 KB Output is correct
6 Correct 70 ms 6776 KB Output is correct
7 Correct 61 ms 6904 KB Output is correct
8 Correct 68 ms 6776 KB Output is correct
9 Correct 60 ms 6520 KB Output is correct
10 Correct 61 ms 6520 KB Output is correct
11 Correct 60 ms 6520 KB Output is correct
12 Correct 63 ms 6520 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 4472 KB Output is correct
2 Correct 104 ms 4688 KB Output is correct
3 Correct 119 ms 4088 KB Output is correct
4 Correct 124 ms 3576 KB Output is correct
5 Correct 147 ms 7932 KB Output is correct
6 Correct 177 ms 7972 KB Output is correct
7 Correct 144 ms 7932 KB Output is correct
8 Correct 207 ms 8132 KB Output is correct
9 Correct 191 ms 8056 KB Output is correct
10 Correct 218 ms 8068 KB Output is correct
11 Correct 156 ms 7800 KB Output is correct
12 Correct 320 ms 7928 KB Output is correct