oj.uz

Submission #567974

# Submission time Handle Problem Language Result Execution time Memory
567974 2022-05-24T13:03:34 Z urosk Sterilizing Spray (JOI15_sterilizing) C++14
20 / 100
 515 ms 59504 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
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(20);
    for(ll i = 0;i<20;i++) c[i] = a[i] + b[i];
    return c;
}
vector<ll> f(ll x){
    vector<ll> c(20);
    ll y = x;
    for(ll i = 0;i<20;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<19;i++) t[v][i] = t[v][i+1];
        t[v][19] = 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19156 KB Output is correct
2 Correct 13 ms 19412 KB Output is correct
3 Correct 17 ms 19768 KB Output is correct
4 Incorrect 19 ms 19688 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 39732 KB Output is correct
2 Correct 168 ms 33936 KB Output is correct
3 Correct 179 ms 50252 KB Output is correct
4 Correct 250 ms 58328 KB Output is correct
5 Correct 289 ms 59504 KB Output is correct
6 Correct 288 ms 59316 KB Output is correct
7 Correct 307 ms 59468 KB Output is correct
8 Correct 287 ms 59200 KB Output is correct
9 Correct 280 ms 59076 KB Output is correct
10 Correct 271 ms 59136 KB Output is correct
11 Correct 285 ms 59152 KB Output is correct
12 Correct 292 ms 59180 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 21872 KB Output is correct
2 Correct 91 ms 36140 KB Output is correct
3 Correct 144 ms 36388 KB Output is correct
4 Correct 295 ms 29540 KB Output is correct
5 Correct 492 ms 58036 KB Output is correct
6 Correct 490 ms 57936 KB Output is correct
7 Correct 277 ms 57988 KB Output is correct
8 Correct 515 ms 57784 KB Output is correct
9 Correct 398 ms 57932 KB Output is correct
10 Correct 387 ms 57676 KB Output is correct
11 Correct 411 ms 57840 KB Output is correct
12 Correct 397 ms 57716 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 39920 KB Output is correct
2 Correct 405 ms 40324 KB Output is correct
3 Incorrect 299 ms 37252 KB Output isn't correct
4 Halted 0 ms 0 KB -