제출 #49630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49630		mra2322001	Sterilizing Spray (JOI15_sterilizing)	C++14	0 / 100	5023 ms	9388 KiB

sterilizing

#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i<(n); i++)
#define f1(i, n) for(int i(1); i<=(n); i++)

using namespace std;
typedef long long ll;
const int N = 1e5 + 3;

ll a[N], t[4*N], lazy[4*N], du[4*N];
int q, k, n;

void push(int nod, int l, int r){
    int x = lazy[nod];
    if(lazy[nod]){
        while(x){
            du[nod] = (t[nod])%ll(k);
            t[nod] /= k;
            --x;
        }
    }
    x = lazy[nod];
    lazy[nod] = 0;
    if(l != r){
        lazy[nod << 1] += x;
        lazy[nod << 1 | 1] += x;
    }
}

void up(int nod, int l, int r, int i, ll val){
    push(nod, l, r);
    if(r < i || l > i) return ;
    if(l==r){
        t[nod] = val/k;
        du[nod] = val%k;
        lazy[nod] = 0;
        return ;
    }
    int m = (l + r)/2;
    up(nod << 1, l, m, i, val);
    up(nod << 1 | 1, m + 1, r, i, val);
    du[nod] = du[nod << 1] + du[nod << 1 | 1];
    t[nod] = t[nod << 1] + t[nod << 1 | 1];
}

void chia(int nod, int l, int r, int i, int j){
    if(i > j) return ;
    push(nod, l, r);
    if(r < i || l > j) return ;
    if(l >= i && r <= j){
        ++lazy[nod];
        push(nod, l, r);
        return ;
    }
    int m = (l + r)/2;
    chia(nod << 1, l, m, i, j);
    chia(nod << 1 | 1, m + 1, r, i, j);
    du[nod] = du[nod << 1] + du[nod << 1 | 1];
    t[nod] = t[nod << 1] + t[nod << 1 | 1];
}

ll sum = 0, remain = 0;
void get1(int nod, int l, int r, int i, int j){
    if(i > j) return ;
    push(nod, l, r);
    if(r < i || l > j) return ;
    if(l >= i && r <= j){
        sum += t[nod];
        remain += du[nod];
        return ;
    }
    int m = (l + r)/2;
    get1(nod << 1, l, m, i, j);
    get1(nod << 1 | 1, m + 1, r, i, j);
}

int main(){
    ios_base::sync_with_stdio(0);
   
    cin >> n >> q >> k;
    f1(i, n) cin >> a[i];
    f1(i, n) up(1, 1, n, i, a[i]);
    while(q--){
        int type, i; ll j; cin >> type >> i >> j;
        if(type==1) up(1, 1, n, i, j);
        else if(type==2) chia(1, 1, n, i, j);
        else{
            remain = sum = 0;
            get1(1, 1, n, i, j);
            cout << sum*ll(k) + remain << endl;
        }
    }
}

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