oj.uz

Submission #49630

# Submission time Handle Problem Language Result Execution time Memory
49630 2018-06-01T08:35:05 Z mra2322001 Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 5000 ms 9388 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5018 ms 5696 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 855 ms 5696 KB Output is correct
2 Correct 1106 ms 6176 KB Output is correct
3 Correct 2041 ms 6692 KB Output is correct
4 Execution timed out 5023 ms 6692 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5012 ms 9388 KB Time limit exceeded
2 Halted 0 ms 0 KB -