oj.uz

Submission #330908

# Submission time Handle Problem Language Result Execution time Memory
330908 2020-11-26T21:06:33 Z Sho10 Sterilizing Spray (JOI15_sterilizing) C++14
15 / 100
 5000 ms 3840 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 640 KB Output is correct
8 Correct 11 ms 492 KB Output is correct
9 Correct 12 ms 492 KB Output is correct
10 Correct 12 ms 492 KB Output is correct
11 Correct 12 ms 512 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 54 ms 2284 KB Output is correct
2 Correct 46 ms 2284 KB Output is correct
3 Correct 42 ms 3436 KB Output is correct
4 Correct 52 ms 3692 KB Output is correct
5 Correct 67 ms 3820 KB Output is correct
6 Correct 63 ms 3820 KB Output is correct
7 Correct 62 ms 3820 KB Output is correct
8 Correct 62 ms 3840 KB Output is correct
9 Correct 64 ms 3820 KB Output is correct
10 Correct 61 ms 3820 KB Output is correct
11 Correct 60 ms 3820 KB Output is correct
12 Correct 61 ms 3820 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 492 KB Output is correct
2 Correct 707 ms 1772 KB Output is correct
3 Correct 1107 ms 1772 KB Output is correct
4 Correct 2456 ms 1388 KB Output is correct
5 Execution timed out 5043 ms 3324 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 3716 ms 2400 KB Output is correct
2 Correct 4352 ms 2440 KB Output is correct
3 Correct 2263 ms 2044 KB Output is correct
4 Correct 3308 ms 1512 KB Output is correct
5 Execution timed out 5019 ms 3732 KB Time limit exceeded
6 Halted 0 ms 0 KB -