oj.uz

Submission #853699

# Submission time Handle Problem Language Result Execution time Memory
853699 2023-09-25T03:26:59 Z octane Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 226 ms 212448 KB 
#include<stdio.h>
typedef long long ll;

int n, q;
ll k;
ll arr[100005];
ll tree[400005][100];
ll lazy[400005];

void init(int node, int s, int e){
    if(s==e){
        tree[node][0] = arr[s];
        if(k==1) return;
        int idx = 0;
        while(tree[node][idx]){
            tree[node][idx+1] = tree[node][idx]/k;
            idx++;
        }
        return;
    }
    int m = (s+e)>>1;
    init(2*node, s, m);
    init(2*node+1, m+1, e);
    int idx = 0;
    while(tree[2*node][idx]+tree[2*node+1][idx]){
        tree[node][idx] = tree[2*node][idx]+tree[2*node+1][idx];
        idx++;
        if(k==1) return;
    }
}

void prop(int node, int s, int e){
    if(lazy[node]==0) return;
    int idx = 0;
    while(tree[node][idx]){
        //printf(" %d %d %d %d\n", node, s, e, idx);
        if(idx+lazy[node]>90) tree[node][idx] = 0;
        else tree[node][idx] = tree[node][idx+lazy[node]];
        idx++;
    }
    if(s!=e){
        lazy[2*node] += lazy[node];
        lazy[2*node+1] += lazy[node];
    }
    lazy[node] = 0;
}

void change(int node, int s, int e, int l, ll v){
    prop(node, s, e);
    if(l<s||e<l) return;
    if(s==e){
        //lazy[node] = 0;
        //printf("  %d %d\n", s, v);
        int idx = 0;
        while(tree[node][idx]){
            tree[node][idx] = 0;
            idx++;
        }
        tree[node][0] = v;
        if(k==1) return;
        idx = 0;
        while(tree[node][idx]){
            tree[node][idx+1] = tree[node][idx]/k;
            idx++;
        }
        return;
    }
    int m = (s+e)>>1;
    change(2*node, s, m, l, v);
    change(2*node+1, m+1, e, l, v);
    int idx = 0;
    while(tree[node][idx]){
        tree[node][idx] = 0;
        idx++;
    }
    idx = 0;
    while(tree[2*node][idx]+tree[2*node+1][idx]){
        tree[node][idx] = tree[2*node][idx]+tree[2*node+1][idx];
        idx++;
        if(k==1) return;
    }
}

void update(int node, int s, int e, int l, int r){
    prop(node, s, e);
    if(e<l||r<s) return;
    if(l<=s&&e<=r){
        lazy[node]++;
        prop(node, s, e);
        return;
    }
    int m = (s+e)>>1;
    update(2*node, s, m, l, r);
    update(2*node+1, m+1, e, l, r);
    int idx = 0;
    while(tree[node][idx]){
        tree[node][idx] = 0;
        idx++;
    }
    idx = 0;
    while(tree[2*node][idx]+tree[2*node+1][idx]){
        tree[node][idx] = tree[2*node][idx]+tree[2*node+1][idx];
        idx++;
    }
}

ll query(int node, int s, int e, int l, int r){
    prop(node, s, e);
    if(l<=s&&e<=r) return tree[node][0];
    if(e<l||r<s) return 0;
    int m = (s+e)>>1;
    return query(2*node, s, m, l, r)+query(2*node+1, m+1, e, l, r);
}

void f(int node, int s, int e){
    for(int i=0;tree[node][i]>0;i++) printf(" %lld", tree[node][i]);
    printf("\n");
    printf(" %d %d %lld\n", s, e, lazy[node]);
    if(s==e) return;
    int m = (s+e)>>1;
    f(2*node, s, m);
    f(2*node+1, m+1, e);
}

int main(){
    scanf("%d %d %lld", &n, &q, &k);
    for(int i=1;i<=n;i++) scanf("%lld", &arr[i]);
    init(1, 1, n);
    ll a, b, c;
    while(q--){
        scanf("%lld %lld %lld", &a, &b, &c);
        if(a==1) change(1, 1, n, b, c);
        if(a==2 && k>1) update(1, 1, n, b, c);
        if(a==3) printf("%lld\n", query(1, 1, n, b, c));
        //f(1, 1, n);
    }
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:126:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |     scanf("%d %d %lld", &n, &q, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:127:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |     for(int i=1;i<=n;i++) scanf("%lld", &arr[i]);
      |                           ~~~~~^~~~~~~~~~~~~~~~~
sterilizing.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |         scanf("%lld %lld %lld", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 5 ms 6488 KB Output is correct
5 Correct 5 ms 10844 KB Output is correct
6 Correct 4 ms 10840 KB Output is correct
7 Correct 5 ms 10840 KB Output is correct
8 Correct 5 ms 10840 KB Output is correct
9 Correct 6 ms 10840 KB Output is correct
10 Correct 5 ms 10844 KB Output is correct
11 Correct 5 ms 10840 KB Output is correct
12 Correct 5 ms 10844 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 105808 KB Output is correct
2 Correct 52 ms 105552 KB Output is correct
3 Correct 58 ms 208464 KB Output is correct
4 Correct 69 ms 208764 KB Output is correct
5 Correct 93 ms 208724 KB Output is correct
6 Correct 83 ms 208872 KB Output is correct
7 Correct 80 ms 208724 KB Output is correct
8 Correct 82 ms 208720 KB Output is correct
9 Correct 73 ms 208720 KB Output is correct
10 Correct 75 ms 208812 KB Output is correct
11 Correct 75 ms 208720 KB Output is correct
12 Correct 74 ms 208764 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16988 KB Output is correct
2 Correct 28 ms 106576 KB Output is correct
3 Correct 36 ms 106844 KB Output is correct
4 Correct 75 ms 55636 KB Output is correct
5 Correct 133 ms 210856 KB Output is correct
6 Correct 127 ms 211024 KB Output is correct
7 Correct 81 ms 209972 KB Output is correct
8 Correct 126 ms 211024 KB Output is correct
9 Correct 98 ms 210768 KB Output is correct
10 Correct 102 ms 210852 KB Output is correct
11 Correct 99 ms 210768 KB Output is correct
12 Correct 100 ms 210768 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 106548 KB Output is correct
2 Correct 122 ms 108368 KB Output is correct
3 Correct 121 ms 107600 KB Output is correct
4 Correct 135 ms 56396 KB Output is correct
5 Correct 190 ms 212240 KB Output is correct
6 Correct 200 ms 212304 KB Output is correct
7 Correct 173 ms 212048 KB Output is correct
8 Correct 226 ms 212336 KB Output is correct
9 Correct 170 ms 212036 KB Output is correct
10 Correct 184 ms 212180 KB Output is correct
11 Correct 150 ms 212024 KB Output is correct
12 Correct 224 ms 212448 KB Output is correct