oj.uz

Submission #535902

# Submission time Handle Problem Language Result Execution time Memory
535902 2022-03-11T18:29:16 Z Danilo21 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 211 ms 5708 KB 
#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES" << en
#define no cout << "NO" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) __builtin_popcountll(a)
#define bithigh(a) 63-__builtin_clzll(a)
#define lg bithigh
ll highpow(ll a) { return 1LL << (ll)lg(a); }

using namespace std;

class segtree{
private:
    vector<ll> sum, mx;
    int n;

    void init(int n){
        this->n = n;
        if (highpow(n)^n) this->n = 2*highpow(n);
        this->sum = vector<ll>(2 * this->n, 0);
        this->mx = vector<ll>(2 * this->n, 0);
    }
    void build(int s, int l, int r, ll* arr){
        if (l == r){
            this->sum[s] = this->mx[s] = arr[l];
            return;
        }

        int m = (l + r) / 2;
        build(2*s, l, m, arr);
        build(2*s+1, m+1, r, arr);
        this->sum[s] = this->sum[2*s] + this->sum[2*s+1];
        this->mx[s] = this->mx[2*s] + this->mx[2*s+1];
    }
    void set(int s, int l, int r, int pos, ll x){
        if (l > pos || r < pos) return;
        if (l == r){
            this->sum[s] = this->mx[s] = x;
            return;
        }

        int m = (l + r) / 2;
        set(2*s, l, m, pos, x);
        set(2*s+1, m+1, r, pos, x);
        this->sum[s] = this->sum[2*s] + this->sum[2*s+1];
        this->mx[s] = this->mx[2*s] + this->mx[2*s+1];
    }
    void update(int s, int l, int r, int ul, int ur, ll x){
        if (l > ur || r < ul || !this->mx[s]) return;
        if (l == r){
            this->sum[s] = this->mx[s] = this->sum[s] / x;
            return;
        }

        int m = (l + r) / 2;
        update(2*s, l, m, ul, ur, x);
        update(2*s+1, m+1, r, ul, ur, x);
        this->sum[s] = this->sum[2*s] + this->sum[2*s+1];
        this->mx[s] = this->mx[2*s] + this->mx[2*s+1];
    }
    ll query(int s, int l, int r, int ql, int qr) {
        if (l > qr || r < ql) return 0;
        if (l >= ql && r <= qr) return this->sum[s];

        int m = (l + r) / 2;
        return query(2*s, l, m, ql, qr) + query(2*s+1, m+1, r, ql, qr);
    }
public:
    segtree(int n, ll* arr){ init(n); build(1, 0, this->n-1, arr); }
    void set(int pos, ll x){ set(1, 0, this->n-1, pos, x); }
    void update(int l, int r, ll x){ update(1, 0, this->n-1, l, r, x); }
    ll query(int l, int r){ if (l>r) return 0; return query(1, 0, this->n-1, l, r); }
};

const ll LINF = 4e18;
const int mxN = 2e5+10, INF = 2e9, mod = (1 ? 1e9+7 : 998244353);
ll n, q, m, a[mxN];
segtree* st;

void Solve(){

    cin >> n >> q >> m;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    st = new segtree(n, a);
    while (q--){
        ri(t); ri(l); ri(r);
        l--;
        if (t == 1) st->set(l, r);
        if (t == 2){
            r--;
            if (m^1) st->update(l, r, m);
        }
        if (t == 3){
            r--;
            cout << st->query(l, r) << en;
        }
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0); cerr.tie(0);
    cout << setprecision(12) << fixed;
    cerr << setprecision(12) << fixed;
    cerr << "Started!" << endl;

    int t = 1;
    //cin >> t;
    while (t--)
        Solve();

    return 0;
}

Compilation message

sterilizing.cpp: In function 'long long int highpow(long long int)':
sterilizing.cpp:26:22: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   26 | #define bithigh(a) 63-__builtin_clzll(a)
      |                      ^
sterilizing.cpp:27:12: note: in expansion of macro 'bithigh'
   27 | #define lg bithigh
      |            ^~~~~~~
sterilizing.cpp:28:38: note: in expansion of macro 'lg'
   28 | ll highpow(ll a) { return 1LL << (ll)lg(a); }
      |                                      ^~

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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 ms 416 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 4 ms 488 KB Output is correct
11 Correct 5 ms 412 KB Output is correct
12 Correct 4 ms 468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 3188 KB Output is correct
2 Correct 49 ms 3016 KB Output is correct
3 Correct 35 ms 5232 KB Output is correct
4 Correct 48 ms 5540 KB Output is correct
5 Correct 55 ms 5628 KB Output is correct
6 Correct 60 ms 5600 KB Output is correct
7 Correct 69 ms 5624 KB Output is correct
8 Correct 68 ms 5676 KB Output is correct
9 Correct 54 ms 5708 KB Output is correct
10 Correct 50 ms 5628 KB Output is correct
11 Correct 51 ms 5696 KB Output is correct
12 Correct 57 ms 5632 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 596 KB Output is correct
2 Correct 13 ms 2644 KB Output is correct
3 Correct 24 ms 2760 KB Output is correct
4 Correct 45 ms 1612 KB Output is correct
5 Correct 65 ms 5256 KB Output is correct
6 Correct 56 ms 5252 KB Output is correct
7 Correct 49 ms 5400 KB Output is correct
8 Correct 55 ms 5260 KB Output is correct
9 Correct 53 ms 5284 KB Output is correct
10 Correct 67 ms 5380 KB Output is correct
11 Correct 59 ms 5252 KB Output is correct
12 Correct 62 ms 5236 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2892 KB Output is correct
2 Correct 82 ms 3020 KB Output is correct
3 Correct 97 ms 2788 KB Output is correct
4 Correct 106 ms 1792 KB Output is correct
5 Correct 127 ms 5476 KB Output is correct
6 Correct 143 ms 5472 KB Output is correct
7 Correct 112 ms 5632 KB Output is correct
8 Correct 162 ms 5512 KB Output is correct
9 Correct 162 ms 5516 KB Output is correct
10 Correct 175 ms 5548 KB Output is correct
11 Correct 132 ms 5480 KB Output is correct
12 Correct 211 ms 5612 KB Output is correct