oj.uz

Submission #521377

# Submission time Handle Problem Language Result Execution time Memory
521377 2022-02-02T02:12:57 Z perchuts Sterilizing Spray (JOI15_sterilizing) C++17
5 / 100
 5000 ms 290344 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()?0:x.front();}

void updateNode(int i){
    assert(2*i+1<4*maxn);
    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 173 ms 269632 KB Output is correct
2 Correct 241 ms 270052 KB Output is correct
3 Correct 204 ms 269864 KB Output is correct
4 Correct 314 ms 270080 KB Output is correct
5 Correct 292 ms 269844 KB Output is correct
6 Correct 224 ms 269708 KB Output is correct
7 Correct 285 ms 269724 KB Output is correct
8 Correct 284 ms 269800 KB Output is correct
9 Correct 320 ms 270016 KB Output is correct
10 Correct 272 ms 270004 KB Output is correct
11 Correct 281 ms 270136 KB Output is correct
12 Correct 275 ms 269928 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 269820 KB Output is correct
2 Correct 439 ms 270152 KB Output is correct
3 Correct 500 ms 270240 KB Output is correct
4 Correct 844 ms 270080 KB Output is correct
5 Correct 1842 ms 271008 KB Output is correct
6 Correct 1901 ms 271056 KB Output is correct
7 Execution timed out 5046 ms 286160 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 2627 ms 272832 KB Output is correct
2 Correct 2644 ms 271004 KB Output is correct
3 Correct 4862 ms 282376 KB Output is correct
4 Correct 3426 ms 270984 KB Output is correct
5 Correct 4726 ms 272904 KB Output is correct
6 Execution timed out 5112 ms 272584 KB Time limit exceeded
7 Halted 0 ms 0 KB -