제출 #675969

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
675969		Ronin13	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	3397 ms	14268 KiB

sterilizing

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<ll,ll>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int nmax = 1e5 + 1;
vector <pll> t(4 * nmax);
vector <ll> T(4 * nmax);
vector <ll> a(nmax);

void build(int v, int l, int r){
    if(l == r){
        t[v] = {a[l], l};
        T[v] = a[l];
        return;
    }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v+ 1, m + 1, r);
    t[v] = max(t[v *2 + 1], t[2 * v]);
    T[v] = T[2 * v] + T[2 * v + 1];
}

void update(int v, int l, int r, int pos, ll val){
    if(l > pos || r < pos) return;
    if(l == r){
        t[v].f = T[v] = val;
        return;
    }
    int m = (l + r) / 2;
    update(2 * v, l, m, pos, val);
    update(2 * v + 1, m + 1, r, pos, val);
    t[v] = max(t[2 * v], t[2 * v + 1]);
    T[v] = T[2 * v] + T[2 * v + 1];
}

pll get(int v, int l, int r, int st, int fin){
    if(l > fin || r < st) return {0, 0};
    if(l >= st && r <= fin)
        return t[v];
    int m = (l + r) /2;
    pll x = get(2 * v, l, m, st, fin);
    pll y = get(2 * v + 1, m + 1, r, st, fin);
    return max(x, y);
}
ll get1(int v, int l, int r, int st, int fin){
    if(l > fin || r < st) return 0;
    if(l >= st && r <= fin)
        return T[v];
    int m = (l + r) /2;
    ll x = get1(2 * v, l, m, st, fin);
    ll y = get1(2 * v + 1, m + 1, r, st, fin);
    return x + y;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, q, k; cin >> n >> q >> k;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    build(1,1, n);
    while(q--){
        int t; cin >> t;
        if(t == 1){
            int pos, val; cin >> pos >> val;
            update(1, 1, n, pos, val);
            continue;
        }
        if(t == 2){

            vector <pii> vec;
            int l, r; cin >> l >> r;
        if(k == 1) continue;
            while(true){
                pll u = get(1, 1, n, l, r);
                if(!u.f) break;
                u.f /= k;
                update(1, 1, n, u.s, 0);
                vec.pb(u);
            }
            for(auto to : vec)
                update(1, 1, n, to.s, to.f);
            continue;
        }
        if(t == 3){
            int l, r; cin >> l >> r;
            cout << get1(1, 1, n, l, r) << "\n";
        }
    }
    return 0;
}

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