oj.uz

Submission #486912

# Submission time Handle Problem Language Result Execution time Memory
486912 2021-11-13T11:02:50 Z Urvuk3 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 283 ms 9744 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll MAXN=1e6,MAXA=5e6+5,INF=1e9,LINF=1e18;
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define mid (l+r)/2
#define sz(a) int((a).size())
#define all(a) a.begin(),a.end()
#define mod 1000000007LL
#define pb push_back
#define endl "\n"
#define PRINT(x) cerr<<#x<<'-'<<x<<endl<<flush;
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
#define pb push_back
#define pf push_front
#define ppf pop_front
#define ppb pop_back
#define PRINTvec(x) { cerr<<#x<<"-"; for(int i=0;i<sz(x);i++) cerr<<x[i]<<" "; cerr<<endl; }

ll n,m,k,q,x,y,z,res=0,l,r;
string s,t;
vector<int> a;
ifstream input;
ofstream output;

#ifdef ONLINE_JUDGE
    #define input cin
    #define output cout
#endif

struct cvor{
    ll sm,mx,mn;
};

cvor seg[4*MAXN];

void init(int node,int l,int r){
    if(l==r){
        seg[node].sm=a[l];
        seg[node].mx=a[l];
        seg[node].mn=a[l];
        return;
    }
    init(2*node,l,mid); init(2*node+1,mid+1,r);
    seg[node].sm=seg[2*node].sm+seg[2*node+1].sm;
    seg[node].mx=max(seg[2*node].mx,seg[2*node+1].mx);
    seg[node].mn=min(seg[2*node].mn,seg[2*node+1].mn);
}

void update(int node,int l,int r,int idx,int val){
    if(l==r){
        seg[node].sm=val;
        seg[node].mx=val;
        seg[node].mn=val;
        return;
    }
    if(idx<=mid) update(2*node,l,mid,idx,val);
    else update(2*node+1,mid+1,r,idx,val);
    seg[node].sm=seg[2*node].sm+seg[2*node+1].sm;
    seg[node].mx=max(seg[2*node].mx,seg[2*node+1].mx);
    seg[node].mn=min(seg[2*node].mn,seg[2*node+1].mn);
}

void spray(int node,int l,int r,int L,int R){
    if(l>r || l>R || r<L || (seg[node].mx==0 && seg[node].mn==0)) return;
    if(l==r){
        int nov=seg[node].sm/k;
        seg[node].sm=nov;
        seg[node].mx=nov;
        seg[node].mn=nov;
        return;
    }
    spray(2*node,l,mid,L,R); spray(2*node+1,mid+1,r,L,R);
    seg[node].sm=seg[2*node].sm+seg[2*node+1].sm;
    seg[node].mx=max(seg[2*node].mx,seg[2*node+1].mx);
    seg[node].mn=min(seg[2*node].mn,seg[2*node+1].mn);
}

ll query(int node,int l,int r,int L,int R){
    if(L<=l && r<=R) return seg[node].sm;
    ll ret=0;
    if(L<=mid) ret+=query(2*node,l,mid,L,R);
    if(R>mid) ret+=query(2*node+1,mid+1,r,L,R);
    return ret;
}

void solve(){
    cin>>n>>q>>k;
    a.resize(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    init(1,1,n);
    while(q--){
        int type;
        cin>>type;
        if(type==1){
            int a,b;
            cin>>a>>b;
            update(1,1,n,a,b);
        }
        else if(type==2){
            cin>>l>>r;
            if(k==1) continue;
            spray(1,1,n,l,r);
        }
        else{
            cin>>l>>r;
            cout<<query(1,1,n,l,r)<<endl;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
        input.open("D:\\UROS\\Programiranje\\input.in",ios::in);
	output.open("D:\\UROS\\Programiranje\\output.out",ios::out|ios::trunc);
    #endif
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int t;
    //cin>>t;
    t=1;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 4 ms 588 KB Output is correct
6 Correct 4 ms 588 KB Output is correct
7 Correct 4 ms 612 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 4 ms 588 KB Output is correct
10 Correct 4 ms 588 KB Output is correct
11 Correct 4 ms 588 KB Output is correct
12 Correct 4 ms 628 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 4048 KB Output is correct
2 Correct 37 ms 5380 KB Output is correct
3 Correct 35 ms 8708 KB Output is correct
4 Correct 45 ms 9308 KB Output is correct
5 Correct 55 ms 9684 KB Output is correct
6 Correct 76 ms 9744 KB Output is correct
7 Correct 53 ms 9728 KB Output is correct
8 Correct 53 ms 9712 KB Output is correct
9 Correct 52 ms 9668 KB Output is correct
10 Correct 49 ms 9636 KB Output is correct
11 Correct 53 ms 9572 KB Output is correct
12 Correct 70 ms 9540 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 772 KB Output is correct
2 Correct 11 ms 3532 KB Output is correct
3 Correct 14 ms 3532 KB Output is correct
4 Correct 41 ms 1988 KB Output is correct
5 Correct 55 ms 6900 KB Output is correct
6 Correct 58 ms 6916 KB Output is correct
7 Correct 47 ms 7008 KB Output is correct
8 Correct 67 ms 7152 KB Output is correct
9 Correct 51 ms 6916 KB Output is correct
10 Correct 49 ms 7020 KB Output is correct
11 Correct 49 ms 6916 KB Output is correct
12 Correct 48 ms 6936 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 3796 KB Output is correct
2 Correct 90 ms 5408 KB Output is correct
3 Correct 116 ms 4832 KB Output is correct
4 Correct 118 ms 3892 KB Output is correct
5 Correct 133 ms 9488 KB Output is correct
6 Correct 158 ms 9544 KB Output is correct
7 Correct 142 ms 9668 KB Output is correct
8 Correct 180 ms 9604 KB Output is correct
9 Correct 173 ms 9396 KB Output is correct
10 Correct 202 ms 9428 KB Output is correct
11 Correct 140 ms 9416 KB Output is correct
12 Correct 283 ms 9512 KB Output is correct