oj.uz

Submission #776374

# Submission time Handle Problem Language Result Execution time Memory
776374 2023-07-07T19:02:15 Z hyakup Sterilizing Spray (JOI15_sterilizing) C++17
75 / 100
 305 ms 7700 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6484 KB Output is correct
2 Incorrect 3 ms 6484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 7132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 6624 KB Output is correct
2 Correct 31 ms 6848 KB Output is correct
3 Correct 36 ms 6924 KB Output is correct
4 Correct 113 ms 6772 KB Output is correct
5 Correct 139 ms 7520 KB Output is correct
6 Correct 129 ms 7372 KB Output is correct
7 Incorrect 74 ms 7380 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 7076 KB Output is correct
2 Correct 155 ms 7172 KB Output is correct
3 Correct 139 ms 6988 KB Output is correct
4 Correct 209 ms 6988 KB Output is correct
5 Correct 234 ms 7500 KB Output is correct
6 Correct 230 ms 7576 KB Output is correct
7 Correct 212 ms 7500 KB Output is correct
8 Correct 263 ms 7700 KB Output is correct
9 Correct 230 ms 7564 KB Output is correct
10 Correct 252 ms 7532 KB Output is correct
11 Correct 220 ms 7612 KB Output is correct
12 Correct 305 ms 7644 KB Output is correct