oj.uz

Submission #1014955

# Submission time Handle Problem Language Result Execution time Memory
1014955 2024-07-05T19:21:53 Z lambd47 Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 149 ms 8068 KB 
#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, mx;
    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)continue;
            spray(1,1,n,a,b);
        }
        else{
            cout<<query(1,1,n,a,b)<<endl;
        }
    }
 
}
 
int32_t main() { 
    int T = 1;
//    cin >> T;
    while(T--) {
        solve();
    }
 
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2396 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 99 ms 5240 KB Output is correct
2 Correct 81 ms 5064 KB Output is correct
3 Correct 106 ms 7508 KB Output is correct
4 Correct 89 ms 7764 KB Output is correct
5 Correct 106 ms 7744 KB Output is correct
6 Correct 104 ms 7764 KB Output is correct
7 Correct 149 ms 7764 KB Output is correct
8 Correct 105 ms 8068 KB Output is correct
9 Correct 138 ms 7896 KB Output is correct
10 Correct 115 ms 7764 KB Output is correct
11 Correct 135 ms 7764 KB Output is correct
12 Correct 132 ms 7764 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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