oj.uz

Submission #330902

# Submission time Handle Problem Language Result Execution time Memory
330902 2020-11-26T20:59:08 Z Sho10 Sterilizing Spray (JOI15_sterilizing) C++14
15 / 100
 5000 ms 6124 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(ll node,ll l,ll 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(ll node,ll l,ll r,ll pos,ll 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(ll node,ll l,ll r,ll st,ll dr){
if(st>r){
    return;
}
if(dr<l){
    return;
}
if(l==r){
    tree[node]/=k;
    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(ll node,ll l,ll r,ll st,ll 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 6 ms 492 KB Output is correct
5 Correct 12 ms 492 KB Output is correct
6 Correct 12 ms 492 KB Output is correct
7 Correct 11 ms 492 KB Output is correct
8 Correct 13 ms 492 KB Output is correct
9 Correct 14 ms 492 KB Output is correct
10 Correct 12 ms 492 KB Output is correct
11 Correct 11 ms 492 KB Output is correct
12 Correct 12 ms 492 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 4076 KB Output is correct
2 Correct 48 ms 3692 KB Output is correct
3 Correct 44 ms 4972 KB Output is correct
4 Correct 53 ms 5740 KB Output is correct
5 Correct 63 ms 6124 KB Output is correct
6 Correct 66 ms 6124 KB Output is correct
7 Correct 63 ms 6124 KB Output is correct
8 Correct 63 ms 6124 KB Output is correct
9 Correct 60 ms 5996 KB Output is correct
10 Correct 64 ms 6124 KB Output is correct
11 Correct 62 ms 5996 KB Output is correct
12 Correct 60 ms 6016 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 1132 KB Output is correct
2 Correct 707 ms 2284 KB Output is correct
3 Correct 1110 ms 2284 KB Output is correct
4 Correct 2474 ms 2596 KB Output is correct
5 Execution timed out 5065 ms 4320 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 3758 ms 3900 KB Output is correct
2 Correct 4368 ms 4132 KB Output is correct
3 Correct 2272 ms 3484 KB Output is correct
4 Correct 3337 ms 3436 KB Output is correct
5 Execution timed out 5063 ms 5492 KB Time limit exceeded
6 Halted 0 ms 0 KB -