oj.uz

Submission #563193

# Submission time Handle Problem Language Result Execution time Memory
563193 2022-05-16T13:19:17 Z zaneyu Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 246 ms 7744 KB 
/*input
5 10 3
1
2
8
1
3
1 2 5
2 3 5
3 2 5
2 1 4
1 3 2
3 3 5
1 2 4
2 1 2
1 1 4
3 1 5
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;
#define ld double
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
const ll maxn=5e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define MP make_pair
ll mult(ll a,ll b){
    ll res=0LL;
    while(b){
        if(b&1) res=(res+a)%MOD;
        a=(a+a)%MOD;
        b>>=1;
    }
    return res%MOD;
}
ll mypow(ll a,ll b){
    ll res=1LL;
    while(b){
        if(b&1) res=res*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return res;
}
struct node{
    int mx=0;
    ll sum=0;
}seg[4*maxn];
int arr[maxn];
node pull(node a,node b){
    node c;
    c.mx=max(a.mx,b.mx);
    c.sum=a.sum+b.sum;
    return c;
}
void build(int idx,int l,int r){
    if(l==r){
        seg[idx].mx=seg[idx].sum=arr[l];
        return;
    }
    int mid=(l+r)/2;
    build(idx*2,l,mid);
    build(idx*2+1,mid+1,r);
    seg[idx]=pull(seg[idx*2],seg[idx*2+1]);
}
void mdf(int idx,int l,int r,int p,int x){
    if(r<p or l>p) return;
    if(l==r){
        seg[idx].mx=seg[idx].sum=x;
        return;
    }
    int mid=(l+r)/2;
    mdf(idx*2,l,mid,p,x);
    mdf(idx*2+1,mid+1,r,p,x);
    seg[idx]=pull(seg[idx*2],seg[idx*2+1]);    
}
void spray(int idx,int l,int r,int ql,int qr,int k){
    if(r<ql or l>qr) return;
    if(seg[idx].mx==0){
        return;
    }
    if(l==r){
        seg[idx].mx/=k;
        seg[idx].sum/=k;
        return;
    }
    int mid=(l+r)/2;
    spray(idx*2,l,mid,ql,qr,k);
    spray(idx*2+1,mid+1,r,ql,qr,k);
    seg[idx]=pull(seg[idx*2],seg[idx*2+1]);    
}
ll query(int idx,int l,int r,int ql,int qr){
    if(r<ql or l>qr) return 0;
    if(ql<=l and r<=qr){
        return seg[idx].sum;
    }
    int mid=(l+r)/2;
    return query(idx*2,l,mid,ql,qr)+query(idx*2+1,mid+1,r,ql,qr);
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,q;
    cin>>n>>q;
    int k;
    cin>>k;
    REP(i,n){
        cin>>arr[i];
    }
    build(1,0,n-1);
    REP(i,q){
        int x,a,b;
        cin>>x>>a>>b;
        --a;
        if(x==2){
            --b;
            if(k==1) continue;
            spray(1,0,n-1,a,b,k);
        }
        else if(x==1){
            mdf(1,0,n-1,a,b);
        }
        else{
            --b;
            cout<<query(1,0,n-1,a,b)<<'\n';
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 472 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 472 KB Output is correct
8 Correct 3 ms 528 KB Output is correct
9 Correct 5 ms 532 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 4 ms 468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 4912 KB Output is correct
2 Correct 39 ms 4476 KB Output is correct
3 Correct 53 ms 6676 KB Output is correct
4 Correct 55 ms 7184 KB Output is correct
5 Correct 61 ms 7744 KB Output is correct
6 Correct 62 ms 7676 KB Output is correct
7 Correct 54 ms 7648 KB Output is correct
8 Correct 63 ms 7648 KB Output is correct
9 Correct 79 ms 7516 KB Output is correct
10 Correct 53 ms 7584 KB Output is correct
11 Correct 53 ms 7616 KB Output is correct
12 Correct 53 ms 7536 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 980 KB Output is correct
2 Correct 14 ms 2808 KB Output is correct
3 Correct 26 ms 2928 KB Output is correct
4 Correct 45 ms 2632 KB Output is correct
5 Correct 54 ms 6236 KB Output is correct
6 Correct 54 ms 6240 KB Output is correct
7 Correct 48 ms 6364 KB Output is correct
8 Correct 69 ms 6368 KB Output is correct
9 Correct 62 ms 6108 KB Output is correct
10 Correct 53 ms 6076 KB Output is correct
11 Correct 50 ms 6140 KB Output is correct
12 Correct 51 ms 6148 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 4260 KB Output is correct
2 Correct 106 ms 4372 KB Output is correct
3 Correct 104 ms 3832 KB Output is correct
4 Correct 107 ms 3424 KB Output is correct
5 Correct 131 ms 7500 KB Output is correct
6 Correct 177 ms 7516 KB Output is correct
7 Correct 120 ms 7436 KB Output is correct
8 Correct 183 ms 7460 KB Output is correct
9 Correct 172 ms 7364 KB Output is correct
10 Correct 218 ms 7484 KB Output is correct
11 Correct 158 ms 7336 KB Output is correct
12 Correct 246 ms 7444 KB Output is correct