oj.uz

Submission #931680

# Submission time Handle Problem Language Result Execution time Memory
931680 2024-02-22T08:58:07 Z parlimoos Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 237 ms 40860 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 = 0 ; bit < 30 ; bit++){
        if(bit + e < 30) seg[i][bit] = seg[i][bit + e];
        else 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;
    bool flg = (k == 1);
    if(flg) k = 2;
    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){
            if(!flg) updSeg(l - 1 , r - 1 , 1);
        }else{
            cout << getSeg(l - 1 , r - 1 , 1) << endl;
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 4 ms 4700 KB Output is correct
6 Correct 4 ms 4700 KB Output is correct
7 Correct 4 ms 4572 KB Output is correct
8 Correct 5 ms 4444 KB Output is correct
9 Correct 5 ms 4444 KB Output is correct
10 Correct 4 ms 4444 KB Output is correct
11 Correct 4 ms 4444 KB Output is correct
12 Correct 5 ms 4444 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 21588 KB Output is correct
2 Correct 70 ms 23120 KB Output is correct
3 Correct 83 ms 39652 KB Output is correct
4 Correct 96 ms 40276 KB Output is correct
5 Correct 114 ms 40860 KB Output is correct
6 Correct 120 ms 40788 KB Output is correct
7 Correct 125 ms 40860 KB Output is correct
8 Correct 115 ms 40788 KB Output is correct
9 Correct 113 ms 40528 KB Output is correct
10 Correct 114 ms 40532 KB Output is correct
11 Correct 118 ms 40516 KB Output is correct
12 Correct 113 ms 40608 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 6488 KB Output is correct
2 Correct 35 ms 21324 KB Output is correct
3 Correct 57 ms 21592 KB Output is correct
4 Correct 137 ms 10840 KB Output is correct
5 Correct 222 ms 37968 KB Output is correct
6 Correct 237 ms 38232 KB Output is correct
7 Correct 101 ms 37976 KB Output is correct
8 Correct 220 ms 37968 KB Output is correct
9 Correct 146 ms 37972 KB Output is correct
10 Correct 150 ms 37812 KB Output is correct
11 Correct 149 ms 37968 KB Output is correct
12 Correct 156 ms 37968 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 21336 KB Output is correct
2 Correct 140 ms 21336 KB Output is correct
3 Correct 94 ms 21336 KB Output is correct
4 Correct 146 ms 11088 KB Output is correct
5 Correct 219 ms 37972 KB Output is correct
6 Correct 221 ms 38004 KB Output is correct
7 Correct 233 ms 38480 KB Output is correct
8 Correct 232 ms 38164 KB Output is correct
9 Correct 160 ms 38268 KB Output is correct
10 Correct 175 ms 38284 KB Output is correct
11 Correct 153 ms 38228 KB Output is correct
12 Correct 180 ms 38228 KB Output is correct