oj.uz

Submission #180298

# Submission time Handle Problem Language Result Execution time Memory
180298 2020-01-08T17:34:57 Z AQT Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 358 ms 9976 KB 
#include <bits/stdc++.h>

using namespace std;

struct node{
    int l, r;
    long long sum, mx;
};

int N, Q, K;
int arr[100005];
node seg[400005];

void pu(int idx){
    seg[idx].sum = seg[2*idx].sum + seg[2*idx+1].sum;
    seg[idx].mx = max(seg[2*idx].mx, seg[2*idx+1].mx);
}

void build(int l, int r, int idx){
    seg[idx].l = l, seg[idx].r = r;
    if(l == r){
        seg[idx].sum = seg[idx].mx = arr[l];
        return;
    }
    int mid = l+r>>1;
    build(l, mid, 2*idx);
    build(mid+1, r, 2*idx+1);
    pu(idx);
}

void upd(int p, int v, int idx){
    if(seg[idx].l == seg[idx].r){
        seg[idx].sum = seg[idx].mx = v;
        return;
    }
    int mid = seg[idx].l+seg[idx].r>>1;
    if(p <= mid){
        upd(p, v, 2*idx);
    }
    else{
        upd(p, v, 2*idx+1);
    }
    pu(idx);
}

void rng(int l, int r, int idx){
    if(seg[idx].mx == 0){
        return;
    }
    if(seg[idx].l == seg[idx].r){
        seg[idx].sum /= K;
        seg[idx].mx /= K;
        return;
    }
    int mid = seg[idx].l + seg[idx].r >> 1;
    if(r <= mid){
        rng(l, r, 2*idx);
    }
    else if(l > mid){
        rng(l, r, 2*idx+1);
    }
    else{
        rng(l, mid, 2*idx);
        rng(mid+1, r, 2*idx+1);
    }
    pu(idx);
}

long long query(int l, int r, int idx){
    if(seg[idx].l == l && seg[idx].r == r){
        return seg[idx].sum;
    }
    int mid = seg[idx].l + seg[idx].r >> 1;
    if(r <= mid){
        query(l, r, 2*idx);
    }
    else if(l > mid){
        query(l, r, 2*idx+1);
    }
    else{
        return query(l, mid, 2*idx) + query(mid+1, r, 2*idx+1);
    }
}

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> Q >> K;
    for(int i = 1; i<=N; i++){
        cin >> arr[i];
    }
    build(1, N, 1);
    while(Q--){
        int c, l, r;
        cin >> c >> l >> r;
        if(c == 1){
            upd(l, r, 1);
        }
        else if(c == 2){
            if(K > 1){
                rng(l, r, 1);
            }
        }
        else {
            cout << query(l, r, 1) << "\n";
        }
    }
}

Compilation message

sterilizing.cpp: In function 'void build(int, int, int)':
sterilizing.cpp:25:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l+r>>1;
               ~^~
sterilizing.cpp: In function 'void upd(int, int, int)':
sterilizing.cpp:36:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = seg[idx].l+seg[idx].r>>1;
               ~~~~~~~~~~^~~~~~~~~~~
sterilizing.cpp: In function 'void rng(int, int, int)':
sterilizing.cpp:55:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = seg[idx].l + seg[idx].r >> 1;
               ~~~~~~~~~~~^~~~~~~~~~~~
sterilizing.cpp: In function 'long long int query(int, int, int)':
sterilizing.cpp:73:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = seg[idx].l + seg[idx].r >> 1;
               ~~~~~~~~~~~^~~~~~~~~~~~
sterilizing.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 8 ms 504 KB Output is correct
5 Correct 7 ms 632 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 7 ms 632 KB Output is correct
8 Correct 7 ms 632 KB Output is correct
9 Correct 8 ms 632 KB Output is correct
10 Correct 7 ms 692 KB Output is correct
11 Correct 7 ms 632 KB Output is correct
12 Correct 7 ms 632 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 5948 KB Output is correct
2 Correct 61 ms 5588 KB Output is correct
3 Correct 58 ms 8700 KB Output is correct
4 Correct 72 ms 9336 KB Output is correct
5 Correct 87 ms 9848 KB Output is correct
6 Correct 89 ms 9848 KB Output is correct
7 Correct 88 ms 9976 KB Output is correct
8 Correct 89 ms 9848 KB Output is correct
9 Correct 82 ms 9712 KB Output is correct
10 Correct 80 ms 9720 KB Output is correct
11 Correct 81 ms 9700 KB Output is correct
12 Correct 80 ms 9712 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1272 KB Output is correct
2 Correct 18 ms 3960 KB Output is correct
3 Correct 25 ms 4088 KB Output is correct
4 Correct 61 ms 3320 KB Output is correct
5 Correct 84 ms 8440 KB Output is correct
6 Correct 86 ms 8440 KB Output is correct
7 Correct 75 ms 8568 KB Output is correct
8 Correct 87 ms 8360 KB Output is correct
9 Correct 76 ms 8184 KB Output is correct
10 Correct 77 ms 8312 KB Output is correct
11 Correct 77 ms 8312 KB Output is correct
12 Correct 76 ms 8440 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 5368 KB Output is correct
2 Correct 129 ms 5496 KB Output is correct
3 Correct 162 ms 4968 KB Output is correct
4 Correct 159 ms 3960 KB Output is correct
5 Correct 194 ms 9684 KB Output is correct
6 Correct 240 ms 9596 KB Output is correct
7 Correct 185 ms 9720 KB Output is correct
8 Correct 280 ms 9712 KB Output is correct
9 Correct 229 ms 9644 KB Output is correct
10 Correct 265 ms 9720 KB Output is correct
11 Correct 201 ms 9596 KB Output is correct
12 Correct 358 ms 9540 KB Output is correct