oj.uz

Submission #330916

# Submission time Handle Problem Language Result Execution time Memory
330916 2020-11-26T21:12:16 Z Sho10 Sterilizing Spray (JOI15_sterilizing) C++14
15 / 100
 5000 ms 3948 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;
}
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 7 ms 364 KB Output is correct
5 Correct 11 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 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 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 51 ms 2284 KB Output is correct
2 Correct 45 ms 2156 KB Output is correct
3 Correct 42 ms 3436 KB Output is correct
4 Correct 56 ms 3692 KB Output is correct
5 Correct 67 ms 3776 KB Output is correct
6 Correct 64 ms 3820 KB Output is correct
7 Correct 65 ms 3820 KB Output is correct
8 Correct 79 ms 3820 KB Output is correct
9 Correct 61 ms 3820 KB Output is correct
10 Correct 62 ms 3820 KB Output is correct
11 Correct 60 ms 3820 KB Output is correct
12 Correct 69 ms 3948 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 620 KB Output is correct
2 Correct 704 ms 1900 KB Output is correct
3 Correct 1123 ms 2064 KB Output is correct
4 Correct 2455 ms 1372 KB Output is correct
5 Execution timed out 5047 ms 3436 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 3693 ms 2028 KB Output is correct
2 Correct 4309 ms 2132 KB Output is correct
3 Correct 2269 ms 2284 KB Output is correct
4 Correct 3222 ms 1868 KB Output is correct
5 Execution timed out 5096 ms 3564 KB Time limit exceeded
6 Halted 0 ms 0 KB -