oj.uz

Submission #567976

# Submission time Handle Problem Language Result Execution time Memory
567976 2022-05-24T13:05:20 Z urosk Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 858 ms 81044 KB 
// __builtin_popcount(x)
// __builtin_popcountll(x)
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;

#define maxn 200005
#define lg 35
ll n,q,k;
ll a[maxn];
ll lazy[4*maxn];
vector<ll> t[4*maxn];
vector<ll> mrg(vector<ll> a,vector<ll> b){
    vector<ll> c(lg);
    for(ll i = 0;i<lg;i++) c[i] = a[i] + b[i];
    return c;
}
vector<ll> f(ll x){
    vector<ll> c(lg);
    ll y = x;
    for(ll i = 0;i<lg;i++){
        c[i] = y;
        y/=k;
    }
    return c;
}
void push(ll v,ll tl,ll tr){
    ll x = lazy[v];
    while(lazy[v]>0&&t[v][0]>0){
        for(ll i = 0;i<lg-1;i++) t[v][i] = t[v][i+1];
        t[v][lg-1] = 0;
        lazy[v]--;
    }
    lazy[v] = x;
    if(tl<tr){
        lazy[2*v]+=lazy[v];
        lazy[2*v+1]+=lazy[v];
    }
    lazy[v] = 0;
}
void init(ll v,ll tl,ll tr){
    if(tl==tr){
        t[v] = f(a[tl]);
        return;
    }
    ll mid = (tl+tr)/2;
    init(2*v,tl,mid);
    init(2*v+1,mid+1,tr);
    t[v] = mrg(t[2*v],t[2*v+1]);
}
void upd(ll v,ll tl,ll tr,ll l,ll r){
    push(v,tl,tr);
    if(l>r) return;
    if(tl==l&&tr==r){
        lazy[v]++;
        push(v,tl,tr);
        return;
    }
    ll mid = (tl+tr)/2;
    upd(2*v,tl,mid,l,min(mid,r));
    upd(2*v+1,mid+1,tr,max(mid+1,l),r);
    push(2*v,tl,mid);
    push(2*v+1,mid+1,tr);
    t[v] = mrg(t[2*v],t[2*v+1]);
}
ll get(ll v,ll tl,ll tr,ll l,ll r){
    push(v,tl,tr);
    if(l>r) return 0;
    if(tl==l&&tr==r) return t[v][0];
    ll mid = (tl+tr)/2;
    return get(2*v,tl,mid,l,min(mid,r)) + get(2*v+1,mid+1,tr,max(mid+1,l),r);
}
void check(ll v,ll tl,ll tr){
    cerr<<"range: "<<tl<< " "<<tr<<endl;
    for(ll x : t[v]) cerr<<x<< " ";
    cerr<<endl;
    if(tl==tr) return;
    ll mid = (tl+tr)/2;
    check(2*v,tl,mid);
    check(2*v+1,mid+1,tr);
}
void upd2(ll v,ll tl,ll tr,ll i,ll x){
    push(v,tl,tr);
    if(tl==tr){
        t[v] = f(x);
        return;
    }
    ll mid = (tl+tr)/2;
    if(i<=mid) upd2(2*v,tl,mid,i,x);
    else upd2(2*v+1,mid+1,tr,i,x);
    push(2*v,tl,mid);
    push(2*v+1,mid+1,tr);
    t[v] = mrg(t[2*v],t[2*v+1]);
}
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n >> q >> k;
    for(ll i = 1;i<=n;i++) cin >> a[i];
    init(1,1,n);
    while(q--){
        ll tip; cin >> tip;
        if(tip==1){
            ll i,x;
            cin >> i >> x;
            upd2(1,1,n,i,x);
        }else if(tip==2){
            ll l,r; cin >> l >> r;
            if(k==1) continue;
            upd(1,1,n,l,r);
        }else{
            ll l,r; cin >> l >> r;
            cout<<get(1,1,n,l,r)<<endl;
        }
    }
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19156 KB Output is correct
2 Correct 13 ms 19668 KB Output is correct
3 Correct 14 ms 20072 KB Output is correct
4 Correct 27 ms 19932 KB Output is correct
5 Correct 27 ms 20972 KB Output is correct
6 Correct 23 ms 20920 KB Output is correct
7 Correct 23 ms 20860 KB Output is correct
8 Correct 23 ms 20916 KB Output is correct
9 Correct 26 ms 20912 KB Output is correct
10 Correct 23 ms 20916 KB Output is correct
11 Correct 22 ms 20908 KB Output is correct
12 Correct 22 ms 20964 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 48368 KB Output is correct
2 Correct 235 ms 39480 KB Output is correct
3 Correct 252 ms 65540 KB Output is correct
4 Correct 351 ms 77884 KB Output is correct
5 Correct 385 ms 78664 KB Output is correct
6 Correct 397 ms 78668 KB Output is correct
7 Correct 383 ms 78684 KB Output is correct
8 Correct 362 ms 78776 KB Output is correct
9 Correct 372 ms 78792 KB Output is correct
10 Correct 351 ms 78792 KB Output is correct
11 Correct 355 ms 78732 KB Output is correct
12 Correct 339 ms 78768 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 22952 KB Output is correct
2 Correct 112 ms 45680 KB Output is correct
3 Correct 150 ms 45760 KB Output is correct
4 Correct 417 ms 33620 KB Output is correct
5 Correct 621 ms 78320 KB Output is correct
6 Correct 633 ms 78364 KB Output is correct
7 Correct 346 ms 78476 KB Output is correct
8 Correct 645 ms 78488 KB Output is correct
9 Correct 546 ms 78412 KB Output is correct
10 Correct 548 ms 78572 KB Output is correct
11 Correct 510 ms 78444 KB Output is correct
12 Correct 588 ms 78308 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 49552 KB Output is correct
2 Correct 520 ms 50140 KB Output is correct
3 Correct 443 ms 45940 KB Output is correct
4 Correct 562 ms 39852 KB Output is correct
5 Correct 754 ms 80956 KB Output is correct
6 Correct 805 ms 80972 KB Output is correct
7 Correct 858 ms 81032 KB Output is correct
8 Correct 828 ms 81020 KB Output is correct
9 Correct 667 ms 80924 KB Output is correct
10 Correct 694 ms 81044 KB Output is correct
11 Correct 666 ms 80916 KB Output is correct
12 Correct 749 ms 80832 KB Output is correct