oj.uz

Submission #1050844

# Submission time Handle Problem Language Result Execution time Memory
1050844 2024-08-09T15:16:48 Z phong Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 95 ms 7872 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

#define ll long long
//#define int long long
const int nmax = 1e5 + 5, N = 1e6;
const ll oo = 1e9 + 5, base = 311;
const int lg = 17, tx = 26;
const ll mod = 998244353;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n, q, k;
int a[nmax];
struct Seg{
    pii tree[1 << 18];
    void build(int id, int l, int r){
        if(l == r){
            tree[id]= {a[l], a[l]};
            return;
        }
        int mid = r + l >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        tree[id].fi = tree[id << 1].fi + tree[id << 1 | 1].fi;
        tree[id].se = max(tree[id << 1].se, tree[id << 1 | 1].se);
    }
    void update_1(int id, int l, int r, int u, int val){
        if(l > u || r < u) return;
        if(l == r){
            tree[id].fi = val;
            tree[id].se = val;
            return;
        }
        int mid = r + l >> 1;
        update_1(id << 1, l, mid, u, val);
        update_1(id << 1 | 1, mid + 1, r, u, val);
        tree[id].fi = tree[id << 1].fi + tree[id << 1 | 1].fi;
        tree[id].se = max(tree[id << 1].se, tree[id << 1 | 1].se);
    }
    void update_2(int id, int l, int r, int u, int v){
        if(l > v || r < u || u > v || tree[id].se == 0) return;
        if(l == r){
            tree[id].fi = tree[id].se = tree[id].fi / k;
            return;
        }
        int mid = r + l >> 1;
        update_2(id << 1, l, mid,u, v);
        update_2(id << 1 | 1, mid + 1, r, u, v);
        tree[id].fi = tree[id << 1].fi + tree[id << 1 | 1].fi;
        tree[id].se = max(tree[id << 1].se, tree[id << 1 | 1].se);
    }
    ll get(int id, int l, int r, int u, int v){
        if(l >= u && r <= v) return tree[id].fi;
        int mid = r + l >> 1;
        if(mid < u)  return get(id << 1 | 1, mid + 1, r, u, v);
        if(mid + 1 > v) return get(id << 1, l, mid, u, v);
        return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
    }
}tree;

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> q >> k;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    tree.build(1, 1, n);
    while(q--){
        int t, x, y;
        cin >> t >> x >> y;
        if(t == 1){
            tree.update_1(1, 1, n, x, y);
        }
        else if(t == 2){
            if(k == 1) continue;
            tree.update_2(1, 1, n, x, y);
        }
        else cout << tree.get(1, 1, n, x, y) << endl;
//        for(int i = 1; i <= n; ++i) cout << tree.get(1, 1, n, i, i) << ' ';
//        cout << endl;
    }
}
/*

9 4 23 9
5
12 27 14 30
8 19 8 9
6 21 5 7
1 4 4 29
11 20 11 12

*/

Compilation message

sterilizing.cpp: In member function 'void Seg::build(int, int, int)':
sterilizing.cpp:28:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |         int mid = r + l >> 1;
      |                   ~~^~~
sterilizing.cpp: In member function 'void Seg::update_1(int, int, int, int, int)':
sterilizing.cpp:41:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         int mid = r + l >> 1;
      |                   ~~^~~
sterilizing.cpp: In member function 'void Seg::update_2(int, int, int, int, int)':
sterilizing.cpp:53:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |         int mid = r + l >> 1;
      |                   ~~^~~
sterilizing.cpp: In member function 'long long int Seg::get(int, int, int, int, int)':
sterilizing.cpp:61:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |         int mid = r + l >> 1;
      |                   ~~^~~
sterilizing.cpp: At global scope:
sterilizing.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main(){
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 2 ms 2708 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 2 ms 2648 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5024 KB Output is correct
2 Correct 23 ms 6748 KB Output is correct
3 Correct 19 ms 6748 KB Output is correct
4 Correct 24 ms 7300 KB Output is correct
5 Correct 29 ms 7764 KB Output is correct
6 Correct 29 ms 7772 KB Output is correct
7 Correct 34 ms 7872 KB Output is correct
8 Correct 30 ms 7760 KB Output is correct
9 Correct 27 ms 7728 KB Output is correct
10 Correct 27 ms 7512 KB Output is correct
11 Correct 27 ms 7772 KB Output is correct
12 Correct 27 ms 7748 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4696 KB Output is correct
2 Correct 6 ms 4700 KB Output is correct
3 Correct 11 ms 4700 KB Output is correct
4 Correct 23 ms 4700 KB Output is correct
5 Correct 32 ms 4900 KB Output is correct
6 Correct 29 ms 4956 KB Output is correct
7 Correct 24 ms 5080 KB Output is correct
8 Correct 29 ms 6400 KB Output is correct
9 Correct 26 ms 6228 KB Output is correct
10 Correct 29 ms 6236 KB Output is correct
11 Correct 26 ms 6248 KB Output is correct
12 Correct 26 ms 6232 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 4700 KB Output is correct
2 Correct 41 ms 6440 KB Output is correct
3 Correct 41 ms 5924 KB Output is correct
4 Correct 49 ms 6484 KB Output is correct
5 Correct 56 ms 7508 KB Output is correct
6 Correct 66 ms 7500 KB Output is correct
7 Correct 54 ms 7508 KB Output is correct
8 Correct 72 ms 7504 KB Output is correct
9 Correct 66 ms 7504 KB Output is correct
10 Correct 74 ms 7508 KB Output is correct
11 Correct 58 ms 7504 KB Output is correct
12 Correct 95 ms 7444 KB Output is correct