oj.uz

Submission #546857

# Submission time Handle Problem Language Result Execution time Memory
546857 2022-04-08T16:46:19 Z ddy888 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 250 ms 16364 KB 
#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr<<" "<<to_string(H);debug_out(T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long 
#define pb push_back
#define fi first
#define si second
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef tuple<int,int,int> ti;  
template<typename T> bool chmin(T &a, T b) {return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chmax(T &a, T b) {return (b > a) ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int N, Q, K;
int C[100010];

struct node { 
    int s,e,m,val;
    node *l, *r;
    node(int _s, int _e) {
        s = _s, e = _e, m = (s+e)>>1ll;
        val = 0;
        if (s != e) {
            l = new node(s,m);
            r = new node(m+1,e);
        }
    }
    void set(int x, int nv) {
        if (s == e) {
            val = nv;
            return;
        }
        if (x > m) r->set(x, nv);
        else l->set(x, nv);
        val = l->val + r->val;
    }
    void spray(int qs, int qe) {
        if (K == 1 || val == 0) return;
        if (s == e) {
            val /= K;
            return;
        }
        if (qs > m) r->spray(qs, qe);
        else if (qe <= m) l->spray(qs, qe);
        else l->spray(qs, m), r->spray(m+1, qe);
        val = l->val + r->val;
    }
    int sum(int qs, int qe) {
        if (qs == s && qe == e) return val;
        if (qs > m) return r->sum(qs, qe);
        if (qe <= m) return l->sum(qs, qe);
        return l->sum(qs, m) + r->sum(m+1, qe);
    }
} *seg;

signed main() {
    fast;
    cin >> N >> Q >> K;
    seg = new node(1, N);
    for (int i = 1; i <= N; ++i) {
        cin >> C[i];
        seg->set(i, C[i]);
    }
    while (Q--) {
        int op, x, y; cin >> op >> x >> y;
        if (op == 1) {
            seg->set(x, y);
        } else if (op == 2) {
            seg->spray(x, y);
        } else {
            cout << seg->sum(x, y) << '\n';
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 ms 476 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 736 KB Output is correct
7 Correct 4 ms 732 KB Output is correct
8 Correct 4 ms 724 KB Output is correct
9 Correct 4 ms 724 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 3 ms 724 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 7256 KB Output is correct
2 Correct 48 ms 5156 KB Output is correct
3 Correct 61 ms 10816 KB Output is correct
4 Correct 80 ms 13824 KB Output is correct
5 Correct 90 ms 14092 KB Output is correct
6 Correct 105 ms 14028 KB Output is correct
7 Correct 84 ms 14044 KB Output is correct
8 Correct 86 ms 14096 KB Output is correct
9 Correct 74 ms 14120 KB Output is correct
10 Correct 71 ms 14076 KB Output is correct
11 Correct 72 ms 14116 KB Output is correct
12 Correct 72 ms 14068 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1196 KB Output is correct
2 Correct 21 ms 6492 KB Output is correct
3 Correct 28 ms 6660 KB Output is correct
4 Correct 52 ms 4776 KB Output is correct
5 Correct 88 ms 15052 KB Output is correct
6 Correct 92 ms 15024 KB Output is correct
7 Correct 79 ms 15108 KB Output is correct
8 Correct 91 ms 15180 KB Output is correct
9 Correct 74 ms 14960 KB Output is correct
10 Correct 74 ms 14920 KB Output is correct
11 Correct 71 ms 14916 KB Output is correct
12 Correct 74 ms 15020 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 7296 KB Output is correct
2 Correct 97 ms 9164 KB Output is correct
3 Correct 103 ms 7580 KB Output is correct
4 Correct 104 ms 6552 KB Output is correct
5 Correct 145 ms 16272 KB Output is correct
6 Correct 162 ms 16352 KB Output is correct
7 Correct 155 ms 16264 KB Output is correct
8 Correct 208 ms 16316 KB Output is correct
9 Correct 184 ms 16236 KB Output is correct
10 Correct 189 ms 16200 KB Output is correct
11 Correct 151 ms 16204 KB Output is correct
12 Correct 250 ms 16364 KB Output is correct