Submission #776374

#	Time	Username	Problem	Language	Result	Execution time	Memory
776374		hyakup	Sterilizing Spray (JOI15_sterilizing)	C++17	75 / 100	305 ms	7700 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int maxn = 1e5 + 10;
ll v[maxn];
ll n, q, k; 

struct node{
    ll sum, maxi; node( ll sum = 0, ll maxi = 0 ) : sum(sum), maxi(maxi) {}
    node operator + ( node n ){
        node resp;
        resp.maxi = max( maxi, n.maxi );
        resp.sum = sum + n.sum;
        return resp;
    }
} seg[4*maxn];

void build( int pos, int ini, int fim ){
    if( ini == fim ){ seg[pos] = node( v[ini], v[ini] ); return; }
    int l = 2*pos, r = 2*pos + 1;
    int mid = ( ini + fim )/2;
    build( l, ini, mid ); build( r, mid + 1, fim );
    seg[pos] = seg[l] + seg[r];
}

void update1( int pos, int ini, int fim, int id, ll val ){
    if( ini > id || id > fim ) return;
    if( ini == fim ){ seg[pos] = node( val, val ); return; }
    int l = 2*pos, r = 2*pos + 1;
    int mid = ( ini + fim )/2;
    update1( l, ini, mid, id, val ); update1( r, mid + 1, fim, id, val );
    seg[pos] = seg[l] + seg[r];
}

void update2( int pos, int ini, int fim, int ki, int kf ){
    if( ki > fim || ini > kf ) return;
    if( ki <= ini && fim <= kf && seg[pos].maxi == 0 ) return;
    if( ini == fim ){ seg[pos].maxi /= k; seg[pos].sum /= k; return; }
    int l = 2*pos, r = 2*pos + 1;
    int mid = ( ini + fim )/2;
    update2( l, ini, mid, ki, kf ); update2( r, mid + 1, fim, ki, kf );
    seg[pos] = seg[l] + seg[r];
}

ll query( int pos, int ini, int fim, int ki, int kf ){
    if( ki > fim || ini > kf ) return 0;
    if( ki <= ini && fim <= kf ) return seg[pos].sum;
    int l = 2*pos, r = 2*pos + 1;
    int mid = ( ini + fim )/2;
    return query( l, ini, mid, ki, kf ) + query( r, mid + 1, fim, ki, kf );
}
int main(){
    cin >> n >> q >> k;
    for( int i = 1; i <= n; i++ ) cin >> v[i];
    build( 1, 1, n );
    while( q-- ){
        int t; cin >> t;
        if( t == 1 ){
            ll id, val; cin >> id >> val;
            update1( 1, 1, n, id, val );
        }
        if( t == 2 && k != 1 ){
            int l, r; cin >> l >> r;
            update2( 1, 1, n, l, r );
        }
        if( t == 3 ){
            int l, r; cin >> l >> r;
            cout << query( 1, 1, n, l, r ) << endl;
        }
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 75 / 75