oj.uz

Submission #521361

# Submission time Handle Problem Language Result Execution time Memory
521361 2022-02-01T23:57:48 Z perchuts Sterilizing Spray (JOI15_sterilizing) C++17
20 / 100
 432 ms 524292 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);

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; }
pair<ii,vector<ll>>lazy[4*maxn];
int n,q;
ll k;
ll v[maxn],seg[4*maxn];

void build(int i,int l,int r){
    if(l==r){
        seg[i] = v[l];
        ll tmp = v[l];
        while(true&&k!=1){lazy[i].second.pb(tmp/k);if(!(tmp/k))break;tmp/=k;}
        lazy[i].first={-1,0};
        return;
    }
    int md = (l+r)/2;
    build(2*i,l,md);
    build(2*i+1,md+1,r);
    seg[i] = seg[2*i] + seg[2*i+1];
    int j = 0;
    while(true&&k!=1){
        int le = (j>=sz(lazy[2*i].second) ? 0 : lazy[2*i].second[j]);
        int ri = (j>=sz(lazy[2*i+1].second) ? 0 : lazy[2*i+1].second[j++]);
        lazy[i].second.pb(le+ri);
        if(le+ri==0)break; 
    }   
    lazy[i].first={-1,0};
}

void push(int i,int l,int r){
    if(k==1)return;
    auto [ind,add] = lazy[i].first;
    if(!add)return;
    ind = min(sz(lazy[i].second)-1,ind+add);
    seg[i] = lazy[i].second[ind];
    lazy[i].first.second = 0;
    if(l==r)return;
    lazy[2*i].first.second+=add;
    lazy[2*i+1].first.second+=add;
}

void update(int i,int l,int r,int x,int d){
    if(k!=1)push(i,l,r);
    if(l>x||r<x)return;
    if(l==r){
        seg[i] = d;
        lazy[i].second.clear();
        ll tmp = d;
        while(true&&k!=1){lazy[i].second.pb(tmp/k);if(!(tmp/k))break;tmp/=k;}
        lazy[i].first={-1,0};
        return;
    }
    int md = (l+r)/2;
    update(2*i,l,md,x,d);
    update(2*i+1,md+1,r,x,d);
    lazy[i].second.clear();
    int j = 0;
    while(true&&k!=1){
        int le = (j>=sz(lazy[2*i].second) ? 0 : lazy[2*i].second[j]);
        int ri = (j>=sz(lazy[2*i+1].second) ? 0 : lazy[2*i+1].second[j++]);
        lazy[i].second.pb(le+ri);
        if(le+ri==0)break; 
    }   
    seg[i] = seg[2*i] + seg[2*i+1];
    lazy[i].first={-1,0};
}

void update2(int i,int l,int r,int x,int y){
    if(k!=1)push(i,l,r);
    if(l>y||r<x)return;
    if(x<=l&&r<=y){
        lazy[i].first.second++;
        push(i,l,r);
        return;
    }
    int md = (l+r)/2;
    update2(2*i,l,md,x,y);
    update2(2*i+1,md+1,r,x,y);
    seg[i] = seg[2*i] + seg[2*i+1];
}


ll query(int i,int l,int r,int x,int y){
    if(k!=1)push(i,l,r);
    if(l>y||r<x)return 0;
    if(x<=l&&r<=y)return 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 debug(int i,int l,int r){
    if(l==r){
        cout<<l<<" "<<r<<" "<<seg[i]<<endl;return;
    }
    int md = (l+r)/2;
    debug(2*i,l,md);
    debug(2*i+1,md+1,r);
    cout<<l<<" "<<r<<" "<<seg[i]<<endl;
}

int main(){_
    cin>>n>>q>>k;
    for(int i=1;i<=n;i++)cin>>v[i];
    vector<ll>x = {1,2,3,4};
    build(1,1,n);
    while(q--){
        int t,a,b;cin>>t>>a>>b;
        if(t==1){   
            update(1,1,n,a,b);
        }else if(t==2){
            if(k!=1)update2(1,1,n,a,b);
        }else{
            cout<<query(1,1,n,a,b)<<endl;
        }
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 426 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 16504 KB Output is correct
2 Correct 46 ms 16068 KB Output is correct
3 Correct 46 ms 17408 KB Output is correct
4 Correct 54 ms 17972 KB Output is correct
5 Correct 65 ms 18112 KB Output is correct
6 Correct 63 ms 18060 KB Output is correct
7 Correct 65 ms 18072 KB Output is correct
8 Correct 72 ms 18116 KB Output is correct
9 Correct 61 ms 18104 KB Output is correct
10 Correct 60 ms 18168 KB Output is correct
11 Correct 63 ms 18140 KB Output is correct
12 Correct 68 ms 18088 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 13824 KB Output is correct
2 Correct 28 ms 17228 KB Output is correct
3 Correct 42 ms 17388 KB Output is correct
4 Correct 83 ms 16228 KB Output is correct
5 Correct 157 ms 23348 KB Output is correct
6 Correct 179 ms 23320 KB Output is correct
7 Correct 71 ms 17272 KB Output is correct
8 Correct 144 ms 23340 KB Output is correct
9 Correct 141 ms 23224 KB Output is correct
10 Correct 108 ms 23244 KB Output is correct
11 Correct 104 ms 23244 KB Output is correct
12 Correct 103 ms 23148 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 432 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -