oj.uz

Submission #521606

# Submission time Handle Problem Language Result Execution time Memory
521606 2022-02-02T14:32:02 Z perchuts Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 1556 ms 312724 KB 
#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define lim 35
using namespace std;
 
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
 
queue<ll>seg[4*maxn];
int lazy[4*maxn];
int n,q,k;
 
ll front(queue<ll>& x){return x.empty()?0LL:x.front();}
 
void updateNode(int i){
    queue<ll>l = seg[2*i], r = seg[2*i+1];
    if(sz(l)<sz(r))swap(l,r);
    while(!seg[i].empty())seg[i].pop();
    while(!l.empty()){
        ll sum = front(l) + front(r);
        l.pop();if(!r.empty())r.pop();
        seg[i].push(sum);
    }
}
 
void push(int i,int l,int r){
    if(k==1)return;
    if(l!=r)lazy[2*i]+=lazy[i],lazy[2*i+1]+=lazy[i];
    for(;lazy[i]&&!seg[i].empty();lazy[i]--)seg[i].pop();
    lazy[i] = 0;
}
 
void update(int i,int l,int r,int x,ll d){
    push(i,l,r);
    if(l>x||r<x)return;
    if(l==r){
        while(!seg[i].empty())seg[i].pop();
        for(;d&&sz(seg[i])<lim;d/=k)seg[i].push(d);
        return; 
    }
    int md = (l+r)/2;
    update(2*i,l,md,x,d);
    update(2*i+1,md+1,r,x,d);
    updateNode(i);
}
 
ll query(int i,int l,int r,int x,int y){
    push(i,l,r);
    if(l>y||r<x)return 0;
    if(x<=l&&r<=y)return front(seg[i]);
    int md = (l+r)/2;
    return query(2*i,l,md,x,y) + query(2*i+1,md+1,r,x,y);
}   
 
void spray(int i,int l,int r,int x,int y){
    if(k==1)return;
    push(i,l,r);
    if(l>y||r<x)return;
    if(x<=l&&r<=y){
        lazy[i]++;
        push(i,l,r);
        return;
    }
    int md = (l+r)/2;
    spray(2*i,l,md,x,y);
    spray(2*i+1,md+1,r,x,y);
    updateNode(i);
}
 
 
int main(){_
    cin>>n>>q>>k;
    for(int i=1;i<=n;i++){
        ll x;cin>>x;
        update(1,1,n,i,x);
    }   
    while(q--){
        int t,a,b;cin>>t>>a>>b;
        if(t==1){
            update(1,1,n,a,1LL*b);
        }else if(t==2){
            if(k!=1)spray(1,1,n,a,b);
        }else{
            cout<<query(1,1,n,a,b)<<endl;
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 269768 KB Output is correct
2 Correct 177 ms 270040 KB Output is correct
3 Correct 176 ms 269888 KB Output is correct
4 Correct 197 ms 270100 KB Output is correct
5 Correct 191 ms 269892 KB Output is correct
6 Correct 191 ms 269892 KB Output is correct
7 Correct 187 ms 269896 KB Output is correct
8 Correct 190 ms 269916 KB Output is correct
9 Correct 199 ms 269948 KB Output is correct
10 Correct 205 ms 270168 KB Output is correct
11 Correct 190 ms 269984 KB Output is correct
12 Correct 190 ms 269864 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 987 ms 294696 KB Output is correct
2 Correct 786 ms 287940 KB Output is correct
3 Correct 1081 ms 302816 KB Output is correct
4 Correct 1306 ms 309684 KB Output is correct
5 Correct 1428 ms 312428 KB Output is correct
6 Correct 1451 ms 312316 KB Output is correct
7 Correct 1452 ms 312300 KB Output is correct
8 Correct 1428 ms 312556 KB Output is correct
9 Correct 1386 ms 312724 KB Output is correct
10 Correct 1407 ms 312432 KB Output is correct
11 Correct 1397 ms 312644 KB Output is correct
12 Correct 1425 ms 312436 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 270144 KB Output is correct
2 Correct 351 ms 270492 KB Output is correct
3 Correct 359 ms 270636 KB Output is correct
4 Correct 482 ms 271320 KB Output is correct
5 Correct 761 ms 272156 KB Output is correct
6 Correct 767 ms 272308 KB Output is correct
7 Correct 1372 ms 297508 KB Output is correct
8 Correct 762 ms 272324 KB Output is correct
9 Correct 727 ms 272156 KB Output is correct
10 Correct 740 ms 272064 KB Output is correct
11 Correct 869 ms 272116 KB Output is correct
12 Correct 724 ms 272396 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 274116 KB Output is correct
2 Correct 712 ms 272180 KB Output is correct
3 Correct 801 ms 283336 KB Output is correct
4 Correct 739 ms 272588 KB Output is correct
5 Correct 1018 ms 274356 KB Output is correct
6 Correct 1108 ms 274900 KB Output is correct
7 Correct 1025 ms 274160 KB Output is correct
8 Correct 1257 ms 277264 KB Output is correct
9 Correct 1107 ms 278220 KB Output is correct
10 Correct 1263 ms 281812 KB Output is correct
11 Correct 1085 ms 285424 KB Output is correct
12 Correct 1556 ms 293252 KB Output is correct