Submission #471121

#	Time	Username	Problem	Language	Result	Execution time	Memory
471121		Vladth11	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	483 ms	11432 KiB

sterilizing

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75