oj.uz

Submission #245427

# Submission time Handle Problem Language Result Execution time Memory
245427 2020-07-06T11:55:38 Z bibabas Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 121 ms 8952 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(int v, int tl, int tr, vi &a) {
        if (tl + 1 == tr) return void(t[v] = mp(a[tl], a[tl]));
        int 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(int v, int tl, int tr, int l, int r, int 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;
        }
        int 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(int v, int tl, int tr, int pos, int x) {
        if (tl + 1 == tr) return void(t[v] = mp(x, x));
        int 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);
    }

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

void solve() {
    int n, q, k; cin >> n >> q >> k;
    vi a(n); cin >> a;
    stree t(a);
    while (q--) {
        int 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
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1152 KB Output is correct
2 Correct 20 ms 3840 KB Output is correct
3 Correct 26 ms 3968 KB Output is correct
4 Correct 62 ms 3192 KB Output is correct
5 Correct 81 ms 8952 KB Output is correct
6 Correct 89 ms 8952 KB Output is correct
7 Correct 72 ms 8952 KB Output is correct
8 Correct 96 ms 8884 KB Output is correct
9 Correct 73 ms 8824 KB Output is correct
10 Correct 72 ms 8792 KB Output is correct
11 Correct 73 ms 8800 KB Output is correct
12 Correct 77 ms 8824 KB Output is correct

Subtask #4
0 / 75.0

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