oj.uz

Submission #521374

# Submission time Handle Problem Language Result Execution time Memory
521374 2022-02-02T02:02:58 Z perchuts Sterilizing Spray (JOI15_sterilizing) C++17
5 / 100
 5000 ms 289880 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; }

ll v[maxn];
queue<ll>seg[4*maxn];
int lazy[4*maxn];
int n,q,k;

ll front(queue<ll>x){return x.empty()?0: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;
    for(int j=1;j<=lazy[i];j++)if(!seg[i].empty())seg[i].pop();
    if(l!=r)lazy[2*i]+=lazy[i],lazy[2*i+1]+=lazy[i];
    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){
    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 174 ms 269712 KB Output is correct
2 Correct 246 ms 269972 KB Output is correct
3 Correct 237 ms 269884 KB Output is correct
4 Correct 311 ms 270048 KB Output is correct
5 Correct 296 ms 269856 KB Output is correct
6 Correct 230 ms 269808 KB Output is correct
7 Correct 277 ms 269844 KB Output is correct
8 Correct 314 ms 270060 KB Output is correct
9 Correct 317 ms 269892 KB Output is correct
10 Correct 277 ms 270004 KB Output is correct
11 Correct 272 ms 269992 KB Output is correct
12 Correct 284 ms 269768 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5073 ms 289880 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 269812 KB Output is correct
2 Correct 422 ms 270244 KB Output is correct
3 Correct 507 ms 270224 KB Output is correct
4 Correct 843 ms 270060 KB Output is correct
5 Correct 1839 ms 270896 KB Output is correct
6 Correct 1853 ms 270872 KB Output is correct
7 Execution timed out 5094 ms 286632 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 2563 ms 272708 KB Output is correct
2 Correct 2581 ms 270828 KB Output is correct
3 Correct 4817 ms 282448 KB Output is correct
4 Correct 3142 ms 271160 KB Output is correct
5 Correct 4644 ms 273012 KB Output is correct
6 Execution timed out 5092 ms 274896 KB Time limit exceeded
7 Halted 0 ms 0 KB -