Submission #1286847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286847		monaxia	Sterilizing Spray (JOI15_sterilizing)	C++20	0 / 100	249 ms	113336 KiB

sterilizing

#include <bits/stdc++.h>
// #include <ext/random>
// #include <ext/pb_ds/assoc_container.hpp>

// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define vektor vector

using namespace std;
// using namespace __gnu_pbds; 

using ll = long long;
using ull = unsigned long long;
using ld = long double;

constexpr ull Mod = 1e6 + 3;
constexpr ull sqr = 547;
constexpr ld eps = 1e-9;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random(ll l, ll r) {if(l <= r) return uniform_int_distribution <ll> (l, r)(rng); return -1;} 

ll st[400005][35], lazy[400005];
int n, Q, k;

void push(int idx, int l, int r){
    if(lazy[idx] != 0){
        for(ll j = lazy[idx]; j <= 34; j ++){
            st[idx][j - lazy[idx]] = 0;
            swap(st[idx][j], st[idx][j - lazy[idx]]);
        }
        
        
        if(l != r){
            lazy[idx << 1] += lazy[idx];
            lazy[idx << 1 | 1] += lazy[idx];
        }
        
        lazy[idx] = 0;
    }
}

void update(int idx, int l, int r, int u, int v){
    push(idx, l, r);
    
    if(v < l || r < u) return;
    if(u <= l && r <= v){
        lazy[idx] ++;
        push(idx, l, r);
        
        return;
    }
    
    int mid = (l + r) >> 1;
    
    update(idx << 1, l, mid, u, v);
    update(idx << 1 | 1, mid + 1, r, u, v);
    
    for(int j = 0; j <= 34; j ++) st[idx][j] = st[idx << 1][j] + st[idx << 1 | 1][j];
}

void update2(int idx, int l, int r, int i, int val, int prevval){
    push(idx, l, r);
    
    int val1 = prevval, j = 0;
    
    while(val1 && j <= 34){
        st[idx][j] -= val1;
        val1 /= k;
        j ++;
    }
    
    j = 0;
    val1 = val;
    
    while(val1 && j <= 34){
        st[idx][j] += val1;
        val1 /= k;
        j ++;
    }
    
    if(l == r) return;
    
    int mid = (l + r) >> 1;
    
    if(i <= mid) update2(idx << 1, l, mid, i, val, prevval);
    else update2(idx << 1 | 1, mid + 1, r, i, val, prevval);
    
    for(int j = 0; j <= 30; j ++) st[idx][j] = st[idx << 1][j] + st[idx << 1 | 1][j];
}

ll query(int idx, int l, int r, int u, int v){
    push(idx, l, r);
    
    if(v < l || r < u) return 0;
    if(u <= l && r <= v) return st[idx][0];
    
    int mid = (l + r) >> 1;
    
    return query(idx << 1, l, mid, u, v) + query(idx << 1 | 1, mid + 1, r, u, v);
}

void solve(){
    memset(st, 0, sizeof(st));
    memset(lazy, 0, sizeof(lazy));
    
    cin >> n >> Q >> k;
    
    assert(k != 1);
    
    for(int i = 1; i <= n; i ++) {
        int x;
        cin >> x;
        
        update2(1, 1, n, i, x, 0);
    }
    
    while(Q --){
        int type, l, r;
        cin >> type >> l >> r;
        
        if(type == 1){
            int prevval = query(1, 1, n, l, l);
            update2(1, 1, n, l, r, prevval);
        }
        
        if(type == 2){
            update(1, 1, n, l, r);
        }
        
        if(type == 3) cout << query(1, 1, n, l, r) << "\n";
    }
}  

main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if(fopen("nameholder.inp", "r")){
        freopen("nameholder.inp", "r", stdin);
        freopen("nameholder.out", "w", stdout);
    }

    int t = 1;

    while(t --){
        solve();
    }
}

Compilation message (stderr)

sterilizing.cpp:142:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  142 | main(){
      | ^~~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:147:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         freopen("nameholder.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:148:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |         freopen("nameholder.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75