oj.uz

Submission #920155

# Submission time Handle Problem Language Result Execution time Memory
920155 2024-02-02T06:53:07 Z Bzslayed Sterilizing Spray (JOI15_sterilizing) C++17
15 / 100
 5000 ms 12792 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 (V == 0 || V == 1) 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){
            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 3 ms 600 KB Output is correct
5 Correct 6 ms 808 KB Output is correct
6 Correct 6 ms 600 KB Output is correct
7 Correct 6 ms 604 KB Output is correct
8 Correct 6 ms 600 KB Output is correct
9 Correct 6 ms 600 KB Output is correct
10 Correct 6 ms 600 KB Output is correct
11 Correct 5 ms 600 KB Output is correct
12 Correct 6 ms 600 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 7256 KB Output is correct
2 Correct 41 ms 5456 KB Output is correct
3 Correct 45 ms 9696 KB Output is correct
4 Correct 62 ms 12176 KB Output is correct
5 Correct 69 ms 12760 KB Output is correct
6 Correct 69 ms 12524 KB Output is correct
7 Correct 67 ms 12624 KB Output is correct
8 Correct 65 ms 12676 KB Output is correct
9 Correct 61 ms 12536 KB Output is correct
10 Correct 61 ms 12624 KB Output is correct
11 Correct 61 ms 12436 KB Output is correct
12 Correct 58 ms 12624 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 1360 KB Output is correct
2 Correct 280 ms 4916 KB Output is correct
3 Correct 432 ms 5060 KB Output is correct
4 Correct 958 ms 3760 KB Output is correct
5 Correct 4011 ms 11124 KB Output is correct
6 Correct 3975 ms 11328 KB Output is correct
7 Correct 65 ms 11344 KB Output is correct
8 Correct 3997 ms 11540 KB Output is correct
9 Execution timed out 5013 ms 10720 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1425 ms 7248 KB Output is correct
2 Correct 1642 ms 7760 KB Output is correct
3 Correct 887 ms 5792 KB Output is correct
4 Correct 1257 ms 5332 KB Output is correct
5 Correct 4001 ms 12688 KB Output is correct
6 Correct 4109 ms 12572 KB Output is correct
7 Correct 3994 ms 12792 KB Output is correct
8 Correct 3974 ms 12588 KB Output is correct
9 Execution timed out 5037 ms 11392 KB Time limit exceeded
10 Halted 0 ms 0 KB -