Submission #1050844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050844		phong	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	95 ms	7872 KiB

sterilizing

//#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 (stderr)

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