oj.uz

Submission #1014959

# Submission time Handle Problem Language Result Execution time Memory
1014959 2024-07-05T19:27:50 Z lambd47 Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 64 ms 9448 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long 
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 100001; 
int arr[MX]; 
struct node{
    int soma=0, mx=0;
    node operator+(node aux){
        return {soma+aux.soma,max(mx,aux.mx)};
    }
};

node seg[4*MX];
int potencias[30];

int k;

void build(int pos, int ini, int fim){
    if(ini==fim){
        seg[pos]={arr[ini],arr[ini]};
        return;
    }
    int m=(ini+fim)/2;
    int e=2*pos,d=2*pos+1;
    build(e,ini,m);
    build(d,m+1,fim);
    seg[pos]=seg[e]+seg[d];
}

void updt1(int pos, int ini, int fim, int id, int val){
    if(ini>id || fim<id)return;
    if(ini==fim){
        seg[pos]={val,val};
        return;
    }
    int m=(ini+fim)/2;
    int e=2*pos,d=2*pos+1;
    updt1(e,ini,m,id,val);
    updt1(d,m+1,fim,id,val);
    seg[pos]=seg[e]+seg[d];
}

void spray(int pos,int ini, int fim, int l, int r){
    if(ini>r || fim<l)return;
    if(l<=ini && fim<=r){
        seg[pos].mx/=k;
        if(seg[pos].mx==0){
            seg[pos].soma=0;
            return;
        }
        else if(ini==fim){
            seg[pos].soma=seg[pos].mx;
            return;
        }
    }
    int m=(ini+fim)/2;
    int e=2*pos,d=2*pos+1;
    spray(e,ini,m,l,r);
    spray(d,m+1,fim,l,r);
    seg[pos]=seg[e]+seg[d];
}

int query(int pos, int ini, int fim, int l, int r){
    if(ini>r || fim<l)return 0;
    if(l<=ini && fim<=r){
        return seg[pos].soma;
    }
    int m=(ini+fim)/2;
    int e=2*pos,d=2*pos+1;
    return query(e,ini,m,l,r)+query(d,m+1,fim,l,r);
}

void solve() {
    int n,q;
    cin>>n>>q>>k;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    build(1,1,n);
    while(q--){
        int tipo,a,b;
        cin>>tipo>>a>>b;
        if(tipo==1){
            updt1(1,1,n,a,b);
        }
        else if(tipo==2){
            if(k!=1)
            spray(1,1,n,a,b);
        }
        else{
            cout<<query(1,1,n,a,b)<<"\n";
        }
    }
 
}
 
int32_t main() {
    cin.tie(0)->sync_with_stdio(0); 
    cin.exceptions(cin.failbit);
 
    int T = 1;
//    cin >> T;
    while(T--) {
        solve();
    }
 
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 6472 KB Output is correct
2 Correct 30 ms 6224 KB Output is correct
3 Correct 26 ms 8280 KB Output is correct
4 Correct 37 ms 8752 KB Output is correct
5 Correct 42 ms 9300 KB Output is correct
6 Correct 42 ms 9084 KB Output is correct
7 Correct 41 ms 9312 KB Output is correct
8 Correct 48 ms 9448 KB Output is correct
9 Correct 38 ms 9116 KB Output is correct
10 Correct 38 ms 9040 KB Output is correct
11 Correct 42 ms 9044 KB Output is correct
12 Correct 46 ms 9000 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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