oj.uz

Submission #920160

# Submission time Handle Problem Language Result Execution time Memory
920160 2024-02-02T07:03:56 Z Bzslayed Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 156 ms 12584 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define coutpair(p) cout << p.first << " " << p.second << "\n"

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;

struct node{
    int s, e, m; //range is [s,e], m is the middle point
    ll val; //sum of [s,e]
    node *l, *r; //create two children l and r, where l is [s,m] and [m+1,e]
    node (int S, int E){ //constructor called node
        s = S, e = E, m = (s+e)/2;
        val = 0; //initially all values are 0
	    if (s != e){ //node is not yet a leaf, so create two children
		    l = new node(s, m); //create left child
            r = new node(m+1, e); //create right child
		}
	}

    void spray(int S, int E, ll V){ //increment [S,E] by V
        if (val == 0) return;
        if (s == e){
            val /= V;
            return;
        }
        if (E <= m) l->spray(S, E, V); //[S,E] is in the left child
        else if (S > m) r->spray(S, E, V); //[S,E] is in the right child
        else l->spray(S, m, V), r->spray(m+1, E, V);
        val = l->val + r->val; //update the range sum
    }

    void adjust(int X, ll V){
        if (s == e){
            val = V;
            return;
        }
        else{
            if (X <= m) l->adjust(X, V);
            else r->adjust(X, V);
        }
        val = l->val + r->val; //update the range sum
    }

    ll sum(int S, int E){
        if (s == S && e == E) return val; //case 1
        if (E <= m) return l->sum(S, E); //case 2, recurse to left child
        else if (S >= m+1) return r->sum(S, E); //case 3, recurse to right child
        else return l->sum(S, m) + r->sum(m+1, E); //case 4, split the query range, recurse to both childs
    }
} *root;

int main(){
    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0);

    ll n, q, k, c, s, t, u; cin >> n >> q >> k;
    root = new node(1, n);

    for (int i=1; i<=n; i++){
        cin >> c;
        root->adjust(i, c);
    }

    for (int i=0; i<q; i++){
        cin >> s >> t >> u;
        if (s == 1){
            root->adjust(t, u);
        }
        else if (s == 2){
            if (k == 1) continue;
            root->spray(t, u, k);
        }
        else cout << root->sum(t, u) << "\n";
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 3 ms 856 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 3 ms 600 KB Output is correct
8 Correct 3 ms 600 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 3 ms 600 KB Output is correct
12 Correct 3 ms 600 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 5456 KB Output is correct
2 Correct 37 ms 3928 KB Output is correct
3 Correct 41 ms 7840 KB Output is correct
4 Correct 54 ms 9960 KB Output is correct
5 Correct 64 ms 10164 KB Output is correct
6 Correct 62 ms 10072 KB Output is correct
7 Correct 62 ms 10064 KB Output is correct
8 Correct 67 ms 10268 KB Output is correct
9 Correct 56 ms 10320 KB Output is correct
10 Correct 56 ms 10100 KB Output is correct
11 Correct 67 ms 10348 KB Output is correct
12 Correct 55 ms 10320 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 856 KB Output is correct
2 Correct 14 ms 4440 KB Output is correct
3 Correct 17 ms 4440 KB Output is correct
4 Correct 39 ms 2648 KB Output is correct
5 Correct 62 ms 9816 KB Output is correct
6 Correct 60 ms 9816 KB Output is correct
7 Correct 55 ms 9816 KB Output is correct
8 Correct 67 ms 9816 KB Output is correct
9 Correct 56 ms 10320 KB Output is correct
10 Correct 53 ms 10968 KB Output is correct
11 Correct 54 ms 11088 KB Output is correct
12 Correct 55 ms 11092 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 5396 KB Output is correct
2 Correct 66 ms 5360 KB Output is correct
3 Correct 65 ms 4688 KB Output is correct
4 Correct 77 ms 3664 KB Output is correct
5 Correct 104 ms 10064 KB Output is correct
6 Correct 116 ms 10048 KB Output is correct
7 Correct 96 ms 10064 KB Output is correct
8 Correct 136 ms 10064 KB Output is correct
9 Correct 106 ms 10832 KB Output is correct
10 Correct 119 ms 12368 KB Output is correct
11 Correct 108 ms 12584 KB Output is correct
12 Correct 156 ms 12368 KB Output is correct