oj.uz

답안 #1014952

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1014952 2024-07-05T19:13:52 Z lambd47 Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 99 ms 10344 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, 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() {
    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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 7332 KB Output is correct
2 Correct 60 ms 6740 KB Output is correct
3 Correct 46 ms 9040 KB Output is correct
4 Correct 61 ms 10064 KB Output is correct
5 Correct 74 ms 10344 KB Output is correct
6 Correct 74 ms 10332 KB Output is correct
7 Correct 74 ms 10324 KB Output is correct
8 Correct 74 ms 10320 KB Output is correct
9 Correct 81 ms 10232 KB Output is correct
10 Correct 71 ms 10260 KB Output is correct
11 Correct 99 ms 10072 KB Output is correct
12 Correct 71 ms 10064 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 28 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 91 ms 6740 KB Output isn't correct
2 Halted 0 ms 0 KB -