oj.uz

Submission #931677

# Submission time Handle Problem Language Result Execution time Memory
931677 2024-02-22T08:52:44 Z parlimoos Sterilizing Spray (JOI15_sterilizing) C++14
85 / 100
 245 ms 39472 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];
ll ps[100000];

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 = int(2e9);
    for(int i = 0 ; i < n ; i++) cin >> a[i];
    for(int i = 0 ; i < n ; i++){
        ps[i] = a[i];
        if(i > 0) ps[i] += ps[i - 1];
    }
    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
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 8744 KB Output is correct
2 Correct 36 ms 23384 KB Output is correct
3 Correct 50 ms 23388 KB Output is correct
4 Correct 138 ms 14936 KB Output is correct
5 Correct 228 ms 38000 KB Output is correct
6 Correct 245 ms 38196 KB Output is correct
7 Correct 80 ms 37984 KB Output is correct
8 Correct 227 ms 39252 KB Output is correct
9 Correct 160 ms 39364 KB Output is correct
10 Correct 156 ms 39248 KB Output is correct
11 Correct 152 ms 39248 KB Output is correct
12 Correct 166 ms 39472 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 23388 KB Output is correct
2 Correct 140 ms 23408 KB Output is correct
3 Correct 100 ms 23484 KB Output is correct
4 Correct 179 ms 15444 KB Output is correct
5 Correct 219 ms 38224 KB Output is correct
6 Correct 223 ms 37984 KB Output is correct
7 Correct 237 ms 38484 KB Output is correct
8 Correct 230 ms 38228 KB Output is correct
9 Correct 167 ms 38068 KB Output is correct
10 Correct 172 ms 38224 KB Output is correct
11 Correct 161 ms 38224 KB Output is correct
12 Correct 185 ms 38228 KB Output is correct