oj.uz

답안 #776374

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 77 ms 7132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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