oj.uz

Submission #521370

# Submission time Handle Problem Language Result Execution time Memory
521370 2022-02-02T01:33:19 Z perchuts Sterilizing Spray (JOI15_sterilizing) C++17
20 / 100
 198 ms 30476 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){
        ll le = (j>=sz(lazy[2*i].second) ? 0 : lazy[2*i].second[j]);
        ll 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; 
        j++;
    }   
    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,ll 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){
        ll le = (j>=sz(lazy[2*i].second) ? 0 : lazy[2*i].second[j]);
        ll ri = (j>=sz(lazy[2*i+1].second) ? 0 : lazy[2*i+1].second[j]);
        lazy[i].second.pb(le+ri);
        j++;
        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);
}

int main(){_
    cin>>n>>q>>k;
    for(int i=1;i<=n;i++)cin>>v[i];
    build(1,1,n);
    while(q--){
        int t,a;
        ll 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 Incorrect 9 ms 12876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 16056 KB Output is correct
2 Correct 51 ms 15912 KB Output is correct
3 Correct 47 ms 17220 KB Output is correct
4 Correct 62 ms 17508 KB Output is correct
5 Correct 68 ms 17928 KB Output is correct
6 Correct 72 ms 17940 KB Output is correct
7 Correct 65 ms 17984 KB Output is correct
8 Correct 66 ms 18016 KB Output is correct
9 Correct 64 ms 17892 KB Output is correct
10 Correct 62 ms 17880 KB Output is correct
11 Correct 60 ms 17844 KB Output is correct
12 Correct 63 ms 17892 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 13780 KB Output is correct
2 Correct 28 ms 17228 KB Output is correct
3 Correct 38 ms 17332 KB Output is correct
4 Correct 83 ms 16232 KB Output is correct
5 Correct 198 ms 23380 KB Output is correct
6 Correct 144 ms 23304 KB Output is correct
7 Correct 59 ms 17176 KB Output is correct
8 Correct 155 ms 23320 KB Output is correct
9 Correct 118 ms 23176 KB Output is correct
10 Correct 127 ms 23452 KB Output is correct
11 Correct 106 ms 23344 KB Output is correct
12 Correct 105 ms 23208 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 145 ms 30476 KB Output isn't correct
2 Halted 0 ms 0 KB -