oj.uz

Submission #546855

# Submission time Handle Problem Language Result Execution time Memory
546855 2022-04-08T16:44:16 Z ddy888 Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 105 ms 16560 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) return r->spray(qs, qe);
        else if (qe <= m) return 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 7228 KB Output is correct
2 Correct 57 ms 5076 KB Output is correct
3 Correct 72 ms 10924 KB Output is correct
4 Correct 73 ms 14032 KB Output is correct
5 Correct 85 ms 16440 KB Output is correct
6 Correct 95 ms 16508 KB Output is correct
7 Correct 105 ms 16560 KB Output is correct
8 Correct 85 ms 16448 KB Output is correct
9 Correct 77 ms 16332 KB Output is correct
10 Correct 82 ms 16332 KB Output is correct
11 Correct 95 ms 16412 KB Output is correct
12 Correct 77 ms 16364 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 1108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 7340 KB Output isn't correct
2 Halted 0 ms 0 KB -