oj.uz

Submission #87199

# Submission time Handle Problem Language Result Execution time Memory
87199 2018-11-30T02:04:46 Z tieunhi Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 310 ms 69684 KB 
#include <bits/stdc++.h>
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define ll long long
#define mid (r + l)/2
#define N 100005

using namespace std;

int n, numQuery, k;
struct IntervalTree
{
    ll t[N << 2];
    int mx[N << 2];
    void update(int l, int r, int id, int x, int val)
    {
        if (l == r)
        {
            t[id] = mx[id] = val;
            return;
        }
        if (x <= mid) update(l, mid, id*2, x, val);
        else update(mid+1, r, id*2+1, x, val);
        t[id] = t[id*2] + t[id*2+1];
        mx[id] = max(mx[id*2], mx[id*2+1]);
    }
    void divide(int l, int r, int id, int x, int y)
    {
        if (l > y || r < x) return;
        if (l >= x && r <= y)
        {
            if (mx[id] == 0) return;
            if (l == r)
            {
                t[id] = mx[id] = t[id]/k;
                return;
            }
        }
        divide(l, mid, id*2, x, y);
        divide(mid+1, r, id*2+1, x, y);
        t[id] = t[id*2] + t[id*2+1];
        mx[id] = max(mx[id*2], mx[id*2+1]);
    }
    ll get(int l, int r, int id, int x, int y)
    {
        if (l > y || r < x) return 0;
        if (l >= x && r <= y) return t[id];
        ll a = get(l, mid, id*2, x, y);
        ll b = get(mid+1, r, id*2+1, x, y);
        return a + b;
    }
}t;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    cin >> n >> numQuery >> k;
    FOR(i, 1, n)
    {
        int x; cin >> x;
        t.update(1, n, 1, i, x);
    }
    while (numQuery--)
    {
        int type, x, y; cin >> type >> x >> y;
        if (type == 1)
            t.update(1, n, 1, x, y);
        else if (type == 2 && k > 1)
            t.divide(1, n, 1, x, y);
        else if (type == 3)
            cout <<t.get(1, n, 1, x, y)<<'\n';
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 4 ms 676 KB Output is correct
3 Correct 3 ms 676 KB Output is correct
4 Correct 6 ms 804 KB Output is correct
5 Correct 7 ms 920 KB Output is correct
6 Correct 10 ms 1004 KB Output is correct
7 Correct 10 ms 1112 KB Output is correct
8 Correct 7 ms 1180 KB Output is correct
9 Correct 8 ms 1268 KB Output is correct
10 Correct 7 ms 1340 KB Output is correct
11 Correct 8 ms 1404 KB Output is correct
12 Correct 8 ms 1528 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 5372 KB Output is correct
2 Correct 83 ms 7064 KB Output is correct
3 Correct 67 ms 9984 KB Output is correct
4 Correct 88 ms 12236 KB Output is correct
5 Correct 147 ms 14792 KB Output is correct
6 Correct 96 ms 17244 KB Output is correct
7 Correct 101 ms 19624 KB Output is correct
8 Correct 94 ms 22160 KB Output is correct
9 Correct 84 ms 24356 KB Output is correct
10 Correct 91 ms 26868 KB Output is correct
11 Correct 90 ms 29084 KB Output is correct
12 Correct 89 ms 31500 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 31500 KB Output is correct
2 Correct 28 ms 31500 KB Output is correct
3 Correct 33 ms 31500 KB Output is correct
4 Correct 80 ms 31500 KB Output is correct
5 Correct 117 ms 34648 KB Output is correct
6 Correct 115 ms 36236 KB Output is correct
7 Correct 85 ms 37784 KB Output is correct
8 Correct 113 ms 38940 KB Output is correct
9 Correct 100 ms 40236 KB Output is correct
10 Correct 122 ms 41508 KB Output is correct
11 Correct 98 ms 42848 KB Output is correct
12 Correct 99 ms 44052 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 44300 KB Output is correct
2 Correct 134 ms 46204 KB Output is correct
3 Correct 150 ms 47076 KB Output is correct
4 Correct 150 ms 48176 KB Output is correct
5 Correct 202 ms 52956 KB Output is correct
6 Correct 220 ms 55412 KB Output is correct
7 Correct 185 ms 57904 KB Output is correct
8 Correct 249 ms 60312 KB Output is correct
9 Correct 219 ms 62784 KB Output is correct
10 Correct 228 ms 65264 KB Output is correct
11 Correct 193 ms 67268 KB Output is correct
12 Correct 310 ms 69684 KB Output is correct