oj.uz

Submission #620337

# Submission time Handle Problem Language Result Execution time Memory
620337 2022-08-03T04:55:51 Z 박상훈(#8517) Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 532 ms 104788 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
int n, q, k, a[100100];
struct Node{
    ll a[32];
    Node(){memset(a, 0, sizeof(a));}
    Node(int x){
        a[0] = x;
        for (int i=1;i<32;i++) a[i] = a[i-1] / k;
    }

    void push(int k){
        ll tmp[32];
        for (int i=0;i<32;i++){
            if (i+k>=32) tmp[i] = 0;
            else tmp[i] = a[i+k];
        }
        for (int i=0;i<32;i++) a[i] = tmp[i];
    }

    Node operator + (const Node &N) const{
        Node ret;
        for (int i=0;i<32;i++) ret.a[i] = a[i] + N.a[i];
        return ret;
    }
};

struct Seg{
    Node tree[400400];
    int lazy[400400];
    void init(int i, int l, int r){
        lazy[i] = 0;
        if (l==r) {tree[i] = Node(a[l]); return;}
        int m = (l+r)>>1;
        init(i<<1, l, m); init(i<<1|1, m+1, r);
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }
    void propagate(int i, int l, int r){
        if (!lazy[i]) return;
        tree[i].push(lazy[i]);
        if (l!=r){
            lazy[i<<1] += lazy[i];
            lazy[i<<1|1] += lazy[i];
        }
        lazy[i] = 0;
    }
    void update1(int i, int l, int r, int s, int x){
        propagate(i, l, r);
        if (r<s || s<l) return;
        if (l==r){
            tree[i] = Node(x);
            return;
        }
        int m = (l+r)>>1;
        update1(i<<1, l, m, s, x); update1(i<<1|1, m+1, r, s, x);
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }
    void update2(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i]++;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update2(i<<1, l, m, s, e); update2(i<<1|1, m+1, r, s, e);
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }
    ll query(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if (r<s || e<l) return 0;
        if (s<=l && r<=e) return tree[i].a[0];
        int m = (l+r)>>1;
        return query(i<<1, l, m, s, e) + query(i<<1|1, m+1, r, s, e);
    }
}tree;

int main(){
    scanf("%d %d %d", &n, &q, &k);
    bool flag = 0;
    if (k==1){
        flag = 1;
        k = 2;
    }

    for (int i=1;i<=n;i++) scanf("%d", a+i);
    tree.init(1, 1, n);

    while(q--){
        int op, x, y;
        scanf("%d %d %d", &op, &x, &y);
        if (op==1) tree.update1(1, 1, n, x, y);
        else if (op==2){
            if (flag) continue;
            tree.update2(1, 1, n, x, y);
        }
        else printf("%lld\n", tree.query(1, 1, n, x, y));
    }
    return 0;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     scanf("%d %d %d", &n, &q, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:89:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     for (int i=1;i<=n;i++) scanf("%d", a+i);
      |                            ~~~~~^~~~~~~~~~~
sterilizing.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         scanf("%d %d %d", &op, &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 100484 KB Output is correct
2 Correct 54 ms 100624 KB Output is correct
3 Correct 44 ms 100552 KB Output is correct
4 Correct 49 ms 100612 KB Output is correct
5 Correct 49 ms 100636 KB Output is correct
6 Correct 51 ms 100632 KB Output is correct
7 Correct 51 ms 100696 KB Output is correct
8 Correct 56 ms 100600 KB Output is correct
9 Correct 53 ms 100636 KB Output is correct
10 Correct 51 ms 100704 KB Output is correct
11 Correct 52 ms 100696 KB Output is correct
12 Correct 51 ms 100652 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 101724 KB Output is correct
2 Correct 179 ms 101628 KB Output is correct
3 Correct 141 ms 102164 KB Output is correct
4 Correct 167 ms 102348 KB Output is correct
5 Correct 200 ms 102412 KB Output is correct
6 Correct 185 ms 102476 KB Output is correct
7 Correct 185 ms 102448 KB Output is correct
8 Correct 204 ms 102524 KB Output is correct
9 Correct 176 ms 102500 KB Output is correct
10 Correct 182 ms 102392 KB Output is correct
11 Correct 213 ms 102384 KB Output is correct
12 Correct 179 ms 102460 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 101008 KB Output is correct
2 Correct 118 ms 101464 KB Output is correct
3 Correct 154 ms 101680 KB Output is correct
4 Correct 373 ms 102124 KB Output is correct
5 Correct 459 ms 103620 KB Output is correct
6 Correct 469 ms 103432 KB Output is correct
7 Correct 175 ms 103588 KB Output is correct
8 Correct 488 ms 103456 KB Output is correct
9 Correct 358 ms 103324 KB Output is correct
10 Correct 351 ms 103316 KB Output is correct
11 Correct 366 ms 103420 KB Output is correct
12 Correct 344 ms 103300 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 102188 KB Output is correct
2 Correct 350 ms 103268 KB Output is correct
3 Correct 246 ms 102536 KB Output is correct
4 Correct 394 ms 103060 KB Output is correct
5 Correct 480 ms 104772 KB Output is correct
6 Correct 508 ms 104692 KB Output is correct
7 Correct 501 ms 104788 KB Output is correct
8 Correct 532 ms 104744 KB Output is correct
9 Correct 372 ms 104556 KB Output is correct
10 Correct 386 ms 104640 KB Output is correct
11 Correct 353 ms 104556 KB Output is correct
12 Correct 390 ms 104628 KB Output is correct