oj.uz

Submission #931674

# Submission time Handle Problem Language Result Execution time Memory
931674 2024-02-22T08:45:10 Z parlimoos Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 235 ms 21412 KB 
//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

int n , q , k , a[100000];
arr(30) seg[400001];
int seginf[400001][2] , laz[400001];

arr(30) frm(int e){
    arr(30) res;
    for(int i = 0 ; i < 30 ; i++){
        res[i] = e % k;;
        e /= k;
    }
    return res;
}
void readSeg(int i){
    for(int bit = 0 ; bit < 30 ; bit++) seg[i][bit] = seg[i << 1][bit] + seg[(i << 1) | 1][bit];
}
void buildSeg(int l = 0 , int r = n - 1 , int i = 1){
    seginf[i][0] = l , seginf[i][1] = r , laz[i] = 0;
    if(l == r) seg[i] = frm(a[l]);
    else{
        int c = (r + l - 1) >> 1;
        buildSeg(l , c , i << 1) , buildSeg(c + 1 , r , (i << 1) | 1);
        readSeg(i);
    }
}
void shftSeg(int i , int e){
    for(int bit = e ; bit < 30 ; bit++) seg[i][bit - e] = seg[i][bit];
    for(int bit = 29 ; bit >= 30 - e ; bit--) seg[i][bit] = 0;
}
void pushSeg(int i){
    if(laz[i] == 0) return;
    for(int ch = (i << 1) ; ch <= ((i << 1) | 1) ; ch++){
        laz[ch] += laz[i] , shftSeg(ch , laz[i]);
    }
    laz[i] = 0;
}
void chgSeg(int l , int i , int val){
    if(seginf[i][0] == l and seginf[i][1] == l) seg[i] = frm(val);
    else if(seginf[i][0] <= l and seginf[i][1] >= l){
        pushSeg(i);
        chgSeg(l , i << 1 , val) , chgSeg(l , (i << 1) | 1 , val);
        readSeg(i);
    }
}
void updSeg(int l , int r , int i){
    if(seginf[i][0] >= l and seginf[i][1] <= r) shftSeg(i , 1) , laz[i]++;
    else if(seginf[i][1] >= l and seginf[i][0] <= r){
        pushSeg(i);
        updSeg(l , r , i << 1) , updSeg(l , r , (i << 1) | 1);
        readSeg(i);
    }
}
ll getSeg(int l , int r , int i){
    if(seginf[i][0] >= l and seginf[i][1] <= r){
        ll d = 1 , res = 0;
        for(int bit = 0 ; bit < 30 and d <= int(1e9) ; bit++ , d *= k) res += (d * (1ll * seg[i][bit]));
        return res;
    }else if(seginf[i][1] >= l and seginf[i][0] <= r){
        pushSeg(i);
        return (getSeg(l , r , i << 1) + getSeg(l , r , (i << 1) | 1));
    }
    return 0;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> q >> k;
    for(int i = 0 ; i < n ; i++) cin >> a[i];
    buildSeg();
    for(int i = 0 ; i < q ; i++){
        int op , l , r;
        cin >> op >> l >> r;

        if(op == 1){
            chgSeg(l - 1 , 1 , r);
        }else if(op == 2){
            updSeg(l - 1 , r - 1 , 1);
        }else{
            cout << getSeg(l - 1 , r - 1 , 1) << endl;
        }
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Incorrect 2 ms 4584 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 6720 KB Output is correct
2 Correct 39 ms 21080 KB Output is correct
3 Correct 51 ms 21084 KB Output is correct
4 Incorrect 131 ms 10840 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

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