oj.uz

Submission #931675

# Submission time Handle Problem Language Result Execution time Memory
931675 2024-02-22T08:48:38 Z parlimoos Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 245 ms 40736 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;
    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 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 6716 KB Output is correct
2 Correct 36 ms 21340 KB Output is correct
3 Correct 51 ms 21336 KB Output is correct
4 Correct 138 ms 10840 KB Output is correct
5 Correct 221 ms 39248 KB Output is correct
6 Correct 226 ms 39252 KB Output is correct
7 Incorrect 245 ms 39380 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 126 ms 21500 KB Output is correct
2 Correct 148 ms 23120 KB Output is correct
3 Correct 98 ms 22612 KB Output is correct
4 Correct 149 ms 12896 KB Output is correct
5 Correct 230 ms 40536 KB Output is correct
6 Correct 239 ms 40692 KB Output is correct
7 Correct 223 ms 40532 KB Output is correct
8 Correct 229 ms 40616 KB Output is correct
9 Correct 170 ms 40736 KB Output is correct
10 Correct 168 ms 40528 KB Output is correct
11 Correct 158 ms 40532 KB Output is correct
12 Correct 194 ms 40380 KB Output is correct