oj.uz

Submission #471121

# Submission time Handle Problem Language Result Execution time Memory
471121 2021-09-07T10:13:19 Z Vladth11 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 483 ms 11432 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;

const ll NMAX = 200001;
const ll VMAX = 100001;
const ll INF = (1LL << 60);
const ll HALF = (1LL << 59);
const ll MOD = 30013;
const ll BLOCK = 318;
const ll base = 31;
const ll nr_of_bits = 21;

ll k;

class All{
public:
    struct Node{
        ll nrr;
        ll sum;
        ll maxim;
    };
    Node all[4 * NMAX];
    ll lazy[4 * NMAX];
    Node combine(Node a, Node b){
        Node sol;
        sol.sum = a.sum + b.sum;
        sol.nrr = a.nrr + b.nrr;
        sol.maxim = max(a.maxim, b.maxim);
        return sol;
    }
    void propaga(ll node, ll st, ll dr){
        if(st != dr){
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        if(lazy[node]){
            all[node].maxim = 0;
            all[node].sum = 0;
        }
        lazy[node] = 0;
    }
    void update(ll node, ll st,  ll dr, ll a, ll b){
        propaga(node, st, dr);
        if(st == dr){
            all[node] = {(b % k == 0), b, b};
            return;
        }
        ll mid = (st + dr) / 2;
        if(a <= mid){
            update(node * 2, st, mid, a, b);
        }else{
            update(node * 2 + 1, mid + 1, dr, a, b);
        }
        propaga(node * 2, st, mid);
        propaga(node * 2 + 1, mid + 1, dr);
        all[node] = combine(all[node * 2], all[node * 2 + 1]);
    }
    void imparte(ll node, ll st, ll dr, ll a, ll b){
        propaga(node, st, dr);
        if(a <= st && dr <= b && all[node].maxim < k){
            lazy[node]++;
            return;
        }
        if(st == dr){
            all[node].maxim /= k;
            all[node].sum = all[node].maxim;
            return;
        }
        ll mid = (st + dr) / 2;
        if(a <= mid){
            imparte(node * 2, st, mid, a, b);
        }
        if(b > mid){
            imparte(node * 2 + 1, mid + 1, dr, a, b);
        }
        propaga(node * 2, st, mid);
        propaga(node * 2 + 1, mid + 1, dr);
        all[node] = combine(all[node * 2], all[node * 2 + 1]);
    }
    ll query(ll node, ll st, ll dr, ll a, ll b){
        propaga(node, st, dr);
        if(a <= st && dr <= b)
            return all[node].sum;
        ll mid = (st + dr) / 2;
        ll s = 0;
        if(a <= mid)
            s += query(node * 2, st, mid, a, b);
        if(b > mid)
            s += query(node * 2 + 1, mid + 1, dr, a, b);
        return s;
    }
}st;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n, q, i;
    cin >> n >> q >> k;
    for(i = 1; i <= n; i++){
        ll x;
        cin >> x;
        st.update(1, 1, n, i, x);
    }
    while(q--){
        ll c, l, r;
        cin >> c >> l >> r;
        if(c == 1){
            st.update(1, 1, n, l, r);
        }else if(c == 2){
            if(k != 1)
            st.imparte(1, 1, n, l, r);
        }else{
            cout << st.query(1, 1, n, l, r) << "\n";
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 6 ms 588 KB Output is correct
6 Correct 6 ms 596 KB Output is correct
7 Correct 6 ms 588 KB Output is correct
8 Correct 6 ms 588 KB Output is correct
9 Correct 7 ms 588 KB Output is correct
10 Correct 6 ms 588 KB Output is correct
11 Correct 7 ms 588 KB Output is correct
12 Correct 6 ms 588 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 5320 KB Output is correct
2 Correct 67 ms 6304 KB Output is correct
3 Correct 77 ms 10436 KB Output is correct
4 Correct 97 ms 10912 KB Output is correct
5 Correct 116 ms 11400 KB Output is correct
6 Correct 114 ms 11432 KB Output is correct
7 Correct 126 ms 11344 KB Output is correct
8 Correct 113 ms 11368 KB Output is correct
9 Correct 110 ms 11228 KB Output is correct
10 Correct 103 ms 11288 KB Output is correct
11 Correct 105 ms 11332 KB Output is correct
12 Correct 100 ms 11228 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 852 KB Output is correct
2 Correct 28 ms 4428 KB Output is correct
3 Correct 48 ms 4436 KB Output is correct
4 Correct 97 ms 2396 KB Output is correct
5 Correct 147 ms 8496 KB Output is correct
6 Correct 134 ms 8576 KB Output is correct
7 Correct 95 ms 9248 KB Output is correct
8 Correct 142 ms 10008 KB Output is correct
9 Correct 130 ms 9784 KB Output is correct
10 Correct 120 ms 9796 KB Output is correct
11 Correct 123 ms 9796 KB Output is correct
12 Correct 130 ms 9812 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 4548 KB Output is correct
2 Correct 174 ms 4540 KB Output is correct
3 Correct 203 ms 4548 KB Output is correct
4 Correct 227 ms 2616 KB Output is correct
5 Correct 288 ms 8772 KB Output is correct
6 Correct 286 ms 8744 KB Output is correct
7 Correct 255 ms 8792 KB Output is correct
8 Correct 380 ms 8772 KB Output is correct
9 Correct 323 ms 8752 KB Output is correct
10 Correct 365 ms 8860 KB Output is correct
11 Correct 283 ms 8788 KB Output is correct
12 Correct 483 ms 8764 KB Output is correct