oj.uz

Submission #471120

# Submission time Handle Problem Language Result Execution time Memory
471120 2021-09-07T10:12:17 Z Vladth11 Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 11284 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){
            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 3 ms 332 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 7 ms 588 KB Output is correct
6 Correct 6 ms 668 KB Output is correct
7 Correct 6 ms 660 KB Output is correct
8 Correct 6 ms 660 KB Output is correct
9 Correct 7 ms 660 KB Output is correct
10 Correct 6 ms 592 KB Output is correct
11 Correct 6 ms 584 KB Output is correct
12 Correct 6 ms 588 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5083 ms 6036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1220 KB Output is correct
2 Correct 28 ms 4712 KB Output is correct
3 Correct 38 ms 4708 KB Output is correct
4 Correct 92 ms 3544 KB Output is correct
5 Correct 137 ms 9960 KB Output is correct
6 Correct 137 ms 10096 KB Output is correct
7 Execution timed out 5097 ms 9288 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 6084 KB Output is correct
2 Correct 169 ms 6252 KB Output is correct
3 Correct 203 ms 5820 KB Output is correct
4 Correct 213 ms 4332 KB Output is correct
5 Correct 258 ms 11208 KB Output is correct
6 Correct 298 ms 11188 KB Output is correct
7 Correct 247 ms 11204 KB Output is correct
8 Correct 369 ms 11284 KB Output is correct
9 Correct 328 ms 11076 KB Output is correct
10 Correct 369 ms 11224 KB Output is correct
11 Correct 274 ms 11076 KB Output is correct
12 Correct 496 ms 11068 KB Output is correct