oj.uz

Submission #245430

# Submission time Handle Problem Language Result Execution time Memory
245430 2020-07-06T11:56:25 Z bibabas Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 362 ms 10504 KB 
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
 
#define ll long long
#define ull unsigned ll
#define vi vector<ll>
#define vvi vector<vi>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define ld long double
#define pii pair<ll, ll>
#define mt make_tuple
#define mn(a, b) a = min(a, b)
#define mx(a, b) a = max(a, b)
 
using namespace std;
 
const ll INF = (ll)2e9;
const ll inf = (ll)2e18;
const ld eps = (ld)1e-8;
const ll mod = (ll)998244353;
const ll MAXN = (ll)1e5 + 1;
const ll MAXC = (ll)1e6 + 1;
const ll MAXE = (ll)1000;
const ll MAXLOG = 21;
const ll maxlen = (ll)1e5;
const ll asci = (ll)256;
const ll block = 480;
const ld PI = acos(-1);
const ld e = 2.7182818284;
 
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<
pii,
null_type,
less<pii>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;*/
 
template <class T>
istream& operator >>(istream &in, vector<T> &arr){
    for (T &cnt : arr) {
        in >> cnt;
    }
    return in;
};

struct stree{
    vector<pii> t;

    void build(ll v, ll tl, ll tr, vi &a) {
        if (tl + 1 == tr) return void(t[v] = mp(a[tl], a[tl]));
        ll tm = (tl + tr) / 2;
        build(2 * v, tl, tm, a);
        build(2 * v + 1, tm, tr, a);
        t[v] = mp(max(t[2 * v].first, t[2 * v + 1].first), t[2 * v].second + t[2 * v + 1].second);
    }

    stree(vi &a) {
        t.resize(4 * a.size());
        build(1, 0, a.size(), a);
    }

    void div(ll v, ll tl, ll tr, ll l, ll r, ll x) {
        if (x == 1) return;
        if (tl >= r || l >= tr || !t[v].first) return;
        if (tl + 1 == tr) {
            t[v].first /= x;
            t[v].second /= x;
            return;
        }
        ll tm = (tl + tr) / 2;
        div(2 * v, tl, tm, l, r, x);
        div(2 * v + 1, tm, tr, l, r, x);
        t[v] = mp(max(t[2 * v].first, t[2 * v + 1].first), t[2 * v].second + t[2 * v + 1].second);
    }

    void pt(ll v, ll tl, ll tr, ll pos, ll x) {
        if (tl + 1 == tr) return void(t[v] = mp(x, x));
        ll tm = (tl + tr) / 2;
        if (pos < tm) pt(2 * v, tl, tm, pos, x);
        else pt(2 * v + 1, tm, tr, pos, x);
        t[v] = mp(max(t[2 * v].first, t[2 * v + 1].first), t[2 * v].second + t[2 * v + 1].second);
    }

    ll sum(ll v, ll tl, ll tr, ll l, ll r) {
        if (l <= tl && tr <= r) return t[v].second;
        if (tl >= r || l >= tr) return 0;
        ll tm = (tl + tr) / 2;
        return sum(2 * v, tl, tm, l, r) + sum(2 * v + 1, tm, tr, l, r);
    }
};

void solve() {
    ll n, q, k; cin >> n >> q >> k;
    vi a(n); cin >> a;
    stree t(a);
    while (q--) {
        ll s, l, r; cin >> s >> l >> r;
        if (s == 1) t.pt(1, 0, n, l - 1, r);
        if (s == 2) t.div(1, 0, n, l - 1, r, k);
        if (s == 3) cout << t.sum(1, 0, n, l - 1, r) << "\n";
    }
}

int main() {
    srand(time(0));
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#endif
    cout.precision(30);
    
    solve();
 
    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 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 10 ms 512 KB Output is correct
5 Correct 10 ms 640 KB Output is correct
6 Correct 8 ms 640 KB Output is correct
7 Correct 9 ms 640 KB Output is correct
8 Correct 9 ms 640 KB Output is correct
9 Correct 13 ms 640 KB Output is correct
10 Correct 9 ms 640 KB Output is correct
11 Correct 9 ms 640 KB Output is correct
12 Correct 9 ms 640 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 4216 KB Output is correct
2 Correct 62 ms 4728 KB Output is correct
3 Correct 66 ms 7812 KB Output is correct
4 Correct 75 ms 9844 KB Output is correct
5 Correct 84 ms 10360 KB Output is correct
6 Correct 98 ms 10504 KB Output is correct
7 Correct 93 ms 10360 KB Output is correct
8 Correct 79 ms 10488 KB Output is correct
9 Correct 80 ms 10232 KB Output is correct
10 Correct 76 ms 10232 KB Output is correct
11 Correct 73 ms 10232 KB Output is correct
12 Correct 78 ms 10232 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 768 KB Output is correct
2 Correct 20 ms 3564 KB Output is correct
3 Correct 24 ms 3584 KB Output is correct
4 Correct 57 ms 2168 KB Output is correct
5 Correct 80 ms 7424 KB Output is correct
6 Correct 83 ms 7544 KB Output is correct
7 Correct 67 ms 7544 KB Output is correct
8 Correct 76 ms 7424 KB Output is correct
9 Correct 69 ms 7424 KB Output is correct
10 Correct 72 ms 7424 KB Output is correct
11 Correct 80 ms 7424 KB Output is correct
12 Correct 68 ms 7424 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 4092 KB Output is correct
2 Correct 119 ms 6008 KB Output is correct
3 Correct 154 ms 4988 KB Output is correct
4 Correct 153 ms 4600 KB Output is correct
5 Correct 182 ms 10360 KB Output is correct
6 Correct 212 ms 10236 KB Output is correct
7 Correct 171 ms 10104 KB Output is correct
8 Correct 242 ms 10232 KB Output is correct
9 Correct 230 ms 9976 KB Output is correct
10 Correct 265 ms 9980 KB Output is correct
11 Correct 198 ms 10120 KB Output is correct
12 Correct 362 ms 9988 KB Output is correct