Submission #791372

#	Time	Username	Problem	Language	Result	Execution time	Memory
791372		Cookie	Sterilizing Spray (JOI15_sterilizing)	C++14	75 / 100	230 ms	9960 KiB

sterilizing

#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int mxn = 1e5 + 5, base = 74;
const ll p = 31, mod = 1e9 + 7;
int n, q, k;
ll sm[4 * mxn + 1], mx[4 * mxn + 1], bad[4 * mxn + 1], c[mxn + 1];
void push(int nd){
    if(bad[nd]){
        bad[nd << 1] = bad[nd << 1 | 1] = 1;
        sm[nd << 1] = sm[nd << 1 | 1] = mx[nd << 1] = mx[nd << 1 | 1] = 0;
    }
}
void upd(int nd, int l, int r, int id, int v){
    if(id < l || id > r)return;
    if(l == r){
        sm[nd] = mx[nd] = v;
        bad[nd] = !v;
        return;
    }
    int mid = (l + r) >> 1;
    push(nd);
    upd(nd << 1, l, mid, id, v); upd(nd << 1 | 1, mid + 1, r, id, v);
    sm[nd] = sm[nd << 1] + sm[nd << 1 | 1];
    mx[nd] = max(mx[nd << 1], mx[nd << 1 | 1]);
    bad[nd] = (mx[nd] == 0);
}
void upd2(int nd, int l, int r, int ql, int qr){
    if(ql > r || qr < l)return;
    if(ql <= l && qr >= r){
        if(mx[nd] < k){
            bad[nd] = 1; sm[nd] = 0; mx[nd] = 0;
            return;
        }else if(l == r){
            mx[nd] /= k; sm[nd] /= k; 
            return;
        }
        
    }
    int mid = (l + r) >> 1;
    push(nd);
    upd2(nd << 1, l, mid, ql, qr); upd2(nd << 1 | 1, mid + 1, r, ql, qr);
    sm[nd] = sm[nd << 1] + sm[nd << 1 | 1];
    mx[nd] = max(mx[nd << 1], mx[nd << 1 | 1]);
    bad[nd] = (mx[nd] == 0);
}
ll get(int nd, int l, int r, int ql, int qr){
    if(ql > r || qr < l)return(0);
    if(ql <= l && qr >= r)return(sm[nd]);
    push(nd);
    int mid = (l + r) >> 1;
    return(get(nd << 1, l, mid, ql, qr) + get(nd << 1 | 1, mid + 1, r, ql, qr));
}
void solve2(){
    for(int i = 1; i <= n; i++){
        cin >> c[i];
        upd(1, 1, n, i, c[i]);
    }
    while(q--){
        int idq; cin >> idq;
        if(idq == 1){
            int id, v; cin >> id >> v;
            upd(1, 1, n, id, v);
        }else if(idq == 2){
            int l, r; cin >> l >> r;
            upd2(1, 1, n, l, r);
        }else{
            int l, r; cin >> l >> r;
            cout << get(1, 1, n, l, r) << "\n";
        }
    }
}
ll bit[mxn + 1];
void upd(int p, ll v){
    while(p <= n){
        bit[p] += v; p += p & (-p);
    }
}
ll get(int p){
    ll ans =0 ;
    while(p){
        ans += bit[p]; p -= p & (-p);
    }
    return(0);
}
void solve1(){
    for(int i = 1; i <= n; i++){
        cin >> c[i]; upd(i, c[i]);
    }
    while(q--){
        int idq; cin >> idq;
        if(idq == 1){
            int id, v; cin >> id >> v;
            upd(id, -c[id]); upd(id, v); c[id] = v;
        }else if(idq == 2){
            int l, r; cin >> l >> r;
            
        }else{
            int l, r; cin >> l >> r;
            cout << get(r) - get(l - 1) << "\n";
        }
    }
}

signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q >> k;
    if(k == 1){
        solve1();
    }else{
        solve2();
    }
    return(0);
}

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