oj.uz

Submission #102393

# Submission time Handle Problem Language Result Execution time Memory
102393 2019-03-24T15:36:23 Z Alexa2001 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 317 ms 5848 KB 
#include <bits/stdc++.h>
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)


using namespace std;

/// 17:27

const int Nmax = 1e5 + 5;
typedef long long ll;


int C[Nmax], n, K;


class ST
{
    ll a[Nmax<<2];

public:
    void update(int node, int st, int dr, int pos, int val)
    {
        if(st == dr)
        {
            a[node] = val;
            return;
        }
        if(pos <= mid) update(left_son, st, mid, pos, val);
            else update(right_son, mid+1, dr, pos, val);

        a[node] = a[left_son] + a[right_son];
    }

    void init(int node, int st, int dr)
    {
        if(st == dr)
        {
            a[node] = C[st];
            return;
        }

        init(left_son, st, mid);
        init(right_son, mid+1, dr);

        a[node] = a[left_son] + a[right_son];
    }

    void spray(int node, int st, int dr, int L, int R)
    {
        if(!a[node]) return;
        if(R < st || dr < L) return;

        if(st == dr)
        {
            a[node] /= K;
            return;
        }

        spray(left_son, st, mid, L, R);
        spray(right_son, mid+1, dr, L, R);

        a[node] = a[left_son] + a[right_son];
    }

    ll query(int node, int st, int dr, int L, int R)
    {
        if(L <= st && dr <= R) return a[node];

        ll x = 0, y = 0;
        if(L <= mid) x = query(left_son, st, mid, L, R);
        if(mid < R) y = query(right_son, mid+1, dr, L, R);

        return x + y;
    }

} aint;

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    int i, x, y, tip, q;

    cin >> n >> q >> K;
    for(i=1; i<=n; ++i) cin >> C[i];

    aint.init(1, 1, n);

    while(q--)
    {
        cin >> tip >> x >> y;
        if(tip == 1) aint.update(1, 1, n, x, y);
            else if(tip == 2 && K > 1) aint.spray(1, 1, n, x, y);
                else if(tip == 3) cout << aint.query(1, 1, n, x, y) << '\n';
    }

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 3916 KB Output is correct
2 Correct 108 ms 3548 KB Output is correct
3 Correct 96 ms 4704 KB Output is correct
4 Correct 107 ms 5368 KB Output is correct
5 Correct 126 ms 5716 KB Output is correct
6 Correct 125 ms 5848 KB Output is correct
7 Correct 122 ms 5752 KB Output is correct
8 Correct 145 ms 5844 KB Output is correct
9 Correct 123 ms 5624 KB Output is correct
10 Correct 147 ms 5652 KB Output is correct
11 Correct 116 ms 5624 KB Output is correct
12 Correct 138 ms 5624 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 980 KB Output is correct
2 Correct 26 ms 1792 KB Output is correct
3 Correct 45 ms 2040 KB Output is correct
4 Correct 112 ms 2428 KB Output is correct
5 Correct 123 ms 4348 KB Output is correct
6 Correct 131 ms 4344 KB Output is correct
7 Correct 129 ms 4344 KB Output is correct
8 Correct 141 ms 4296 KB Output is correct
9 Correct 157 ms 4216 KB Output is correct
10 Correct 116 ms 4196 KB Output is correct
11 Correct 111 ms 4188 KB Output is correct
12 Correct 111 ms 4188 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 3448 KB Output is correct
2 Correct 146 ms 3448 KB Output is correct
3 Correct 160 ms 2924 KB Output is correct
4 Correct 172 ms 3108 KB Output is correct
5 Correct 223 ms 5700 KB Output is correct
6 Correct 243 ms 5596 KB Output is correct
7 Correct 202 ms 5540 KB Output is correct
8 Correct 266 ms 5556 KB Output is correct
9 Correct 244 ms 5496 KB Output is correct
10 Correct 312 ms 5440 KB Output is correct
11 Correct 197 ms 5368 KB Output is correct
12 Correct 317 ms 5528 KB Output is correct