oj.uz

Submission #330915

# Submission time Handle Problem Language Result Execution time Memory
330915 2020-11-26T21:11:44 Z Sho10 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 310 ms 5996 KB 
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho10
#define ll long long
#define double long double
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 1000007
#define PI 3.14159265359
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005ll
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll n,q,a[100005],tree[400005],k;
void build(int node,int l,int r){
if(l==r){
    tree[node]=a[l];
    return;
}
ll mid=(l+r)/2;
build(2*node,l,mid);
build(2*node+1,mid+1,r);
tree[node]=tree[node*2]+tree[node*2+1];
}
void update(int node,int l,int r,int pos,int val){
if(l==r){
    tree[node]=val;
    return;
}
ll mid=(l+r)/2;
if(pos<=mid){
    update(2*node,l,mid,pos,val);
}else update(2*node+1,mid+1,r,pos,val);
tree[node]=tree[node*2]+tree[node*2+1];
}
void spray(int node,int l,int r,int st,int dr){
if(st>r){
    return;
}
if(dr<l){
    return;
}
if(l==r){
    tree[node]/=k;
    return;
}
if(st<=l&&r<=dr&&tree[node]==0){
    return;
}
ll mid=(l+r)/2;
if(st<=mid){
    spray(2*node,l,mid,st,dr);
}
if(mid<dr){
    spray(2*node+1,mid+1,r,st,dr);
}
tree[node]=tree[node*2]+tree[node*2+1];
}
ll query(int node,int l,int r,int st,int dr){
if(st<=l&&r<=dr){
    return tree[node];
}
if(st>r){
    return 0;
}
if(dr<l){
    return 0;
}
ll mid=(l+r)/2;
ll res=0;
if(st<=mid){
    res+=query(2*node,l,mid,st,dr);
}
if(mid<dr){
    res+=query(2*node+1,mid+1,r,st,dr);
}
return res;
}
int32_t main(){
CODE_START;
cin>>n>>q>>k;
for(ll i=1;i<=n;i++)
{
    cin>>a[i];
}
build(1,1,n);
while(q--){
    ll type,l,r;
   cin>>type>>l>>r;
    if(type==1){
        update(1,1,n,l,r);
    }else if(type==2){
        if(k>=2)
    spray(1,1,n,l,r);
    }else if(type==3)
    cout<<query(1,1,n,l,r)<<endl;
}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 4 ms 492 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 4 ms 492 KB Output is correct
7 Correct 4 ms 492 KB Output is correct
8 Correct 4 ms 492 KB Output is correct
9 Correct 5 ms 492 KB Output is correct
10 Correct 4 ms 492 KB Output is correct
11 Correct 4 ms 492 KB Output is correct
12 Correct 4 ms 492 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 2412 KB Output is correct
2 Correct 45 ms 2284 KB Output is correct
3 Correct 41 ms 3584 KB Output is correct
4 Correct 66 ms 3820 KB Output is correct
5 Correct 66 ms 3948 KB Output is correct
6 Correct 65 ms 3948 KB Output is correct
7 Correct 64 ms 3948 KB Output is correct
8 Correct 66 ms 3948 KB Output is correct
9 Correct 61 ms 3948 KB Output is correct
10 Correct 67 ms 3948 KB Output is correct
11 Correct 62 ms 3948 KB Output is correct
12 Correct 61 ms 4076 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 748 KB Output is correct
2 Correct 15 ms 1900 KB Output is correct
3 Correct 21 ms 1984 KB Output is correct
4 Correct 71 ms 1388 KB Output is correct
5 Correct 77 ms 4076 KB Output is correct
6 Correct 77 ms 4716 KB Output is correct
7 Correct 60 ms 4844 KB Output is correct
8 Correct 79 ms 4716 KB Output is correct
9 Correct 74 ms 4588 KB Output is correct
10 Correct 73 ms 4588 KB Output is correct
11 Correct 72 ms 4588 KB Output is correct
12 Correct 73 ms 4588 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 2156 KB Output is correct
2 Correct 107 ms 2284 KB Output is correct
3 Correct 123 ms 2156 KB Output is correct
4 Correct 135 ms 1772 KB Output is correct
5 Correct 173 ms 4460 KB Output is correct
6 Correct 179 ms 5996 KB Output is correct
7 Correct 154 ms 5868 KB Output is correct
8 Correct 218 ms 5992 KB Output is correct
9 Correct 201 ms 5836 KB Output is correct
10 Correct 231 ms 5868 KB Output is correct
11 Correct 177 ms 5868 KB Output is correct
12 Correct 310 ms 5996 KB Output is correct