oj.uz

Submission #483653

# Submission time Handle Problem Language Result Execution time Memory
483653 2021-10-31T13:08:48 Z Mahfel Sterilizing Spray (JOI15_sterilizing) C++17
75 / 100
 3166 ms 77692 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MXN = 2e5 + 20 , LOG = 35;
#define lt(x) 2*x+1
#define rt(x) 2*x+2
int n,q,k;
int a[MXN];

struct seg_tree {
    int size;
    vector<ll> v[LOG] , d;
    seg_tree() {
        size = 0;
    }
    void init() {
        size = 1;
        while(size < n) size <<= 1;
        for(int i = 0 ; i < LOG ; i++) v[i].assign(2*size , 0);
        d.assign(2*size , 0);
    }
    void build(int x , int lx , int rx) {
        if(rx-lx == 1) {
            if(lx < n) {
                v[0][x] = a[lx];
                for(int i = 1 ; i < LOG ; i++) {
                    v[i][x] = v[i-1][x]/k;
                }
            }
            return;
        }
        int m = (lx+rx)/2;
        build(lt(x) , lx , m); build(rt(x) , m , rx);
        for(int i = 0 ; i < LOG ; i++) {
            v[i][x] = v[i][lt(x)] + v[i][rt(x)];
        }
    }
    void build() {
        build(0 , 0 , size);
    }

    void shift(int x , int lx , int rx) {
        if(rx-lx == 1) return;
        d[lt(x)] += d[x];
        d[rt(x)] += d[x];
    }
    void update(int x , int lx , int rx) {
        for(int i = 0 ; i < LOG ; i++) {
            v[i][x] = (i+d[x] < LOG ? v[i+d[x]][x] : 0);
        }
        d[x] = 0;
    }

    void set(int x , int lx , int rx , int i , ll t) {
        if(rx-lx == 1) {
            v[0][x] = t;
            for(int i = 1 ; i < LOG ; i++) {
                v[i][x] = v[i-1][x]/k;
            }
            d[x] = 0;
            return;
        }
        shift(x , lx , rx);
        int m = (lx+rx)/2;
        if(i < m) {
            set(lt(x) , lx , m , i , t);
            shift(rt(x) , m , rx); update(rt(x) , m , rx);
        } else {
            set(rt(x) , m , rx , i , t);
            shift(lt(x) , lx , m); update(lt(x) , lx , m);
        }
        d[x] = 0;
        for(int i = 0 ; i < LOG ; i++) v[i][x] = v[i][lt(x)] + v[i][rt(x)];
    }
    void set(int i , ll k) {
        set(0 , 0 , size , i , k);
    }

    void divide(int x , int lx , int rx , int l , int r) {
        if(lx >= l && rx <= r) {
            d[x]++;
            shift(x , lx , rx);
            update(x , lx , rx);
            return;
        }
        if(lx >= r || rx <= l) {
            shift(x , lx , rx);
            update(x , lx , rx);
            return;
        }
        shift(x , lx , rx);
        int m = (lx+rx)/2;
        divide(lt(x) , lx , m , l , r);
        divide(rt(x) , m , rx , l , r);
        d[x] = 0;
        for(int i = 0 ; i < LOG ; i++) v[i][x] = v[i][lt(x)] + v[i][rt(x)];
    }
    void divide(int l , int r) {
        divide(0 , 0 , size , l , r);
    }

    ll sum(int x , int lx , int rx , int l , int r) {
        if(lx >= l && rx <= r) {
            shift(x , lx , rx);
            update(x , lx , rx);
            return d[x] >= LOG ? 0 : v[d[x]][x];
        }
        if(lx >= r || rx <= l) {
            shift(x , lx , rx);
            update(x , lx , rx);
            return 0;
        }
        shift(x , lx , rx);
        int m = (lx+rx)/2;
        ll a = sum(lt(x) , lx , m , l , r) , b = sum(rt(x) , m , rx , l , r);
        d[x] = 0;
        for(int i = 0 ; i < LOG ; i++) v[i][x] = v[i][lt(x)] + v[i][rt(x)];
        return a+b;
    }
    ll sum(int l , int r) {
        return sum(0 , 0 , size , l , r);
    }
} seg;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    cin >> n >> q >> k;
    for(int i = 0 ; i < n ; i++) {
        cin >> a[i];
    }
    seg.init(); seg.build();

    while(q--) {

        int type,x,y; cin >> type >> x >> y;
        if(type == 1) {
            seg.set(x-1 , y);
        }
        if(type == 2) {
            seg.divide(x-1 , y);
        }
        if(type == 3) {
            cout << seg.sum(x-1 , y) << "\n";
        }

    }

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 332 KB Output is correct
2 Incorrect 5 ms 844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 680 ms 5444 KB Output is correct
2 Correct 441 ms 37848 KB Output is correct
3 Correct 677 ms 38068 KB Output is correct
4 Correct 2255 ms 20440 KB Output is correct
5 Correct 2784 ms 76296 KB Output is correct
6 Correct 2776 ms 76372 KB Output is correct
7 Incorrect 2776 ms 76284 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1790 ms 37928 KB Output is correct
2 Correct 2017 ms 39448 KB Output is correct
3 Correct 1260 ms 38980 KB Output is correct
4 Correct 2199 ms 21296 KB Output is correct
5 Correct 2799 ms 77564 KB Output is correct
6 Correct 2785 ms 77516 KB Output is correct
7 Correct 2852 ms 77596 KB Output is correct
8 Correct 2769 ms 77692 KB Output is correct
9 Correct 3133 ms 77448 KB Output is correct
10 Correct 3166 ms 77364 KB Output is correct
11 Correct 3097 ms 77468 KB Output is correct
12 Correct 3034 ms 77568 KB Output is correct