oj.uz

Submission #620366

# Submission time Handle Problem Language Result Execution time Memory
620366 2022-08-03T05:08:13 Z 반딧불(#8518) Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 463 ms 67060 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
ll k;

struct Node{
    ll val[31]; /// 0 ~ 30

    Node(){}
    Node(ll x){
        val[0] = x;
        for(int i=1; i<=30; i++) val[i] = val[i-1] / k;
    }

    Node operator+(const Node &r)const{
        Node tmp;
        for(int i=0; i<=30; i++) tmp.val[i] = val[i] + r.val[i];
        return tmp;
    }

    void rotate(int x){
        for(int i=0; i+x<=30; i++) val[i] = val[i+x];
        for(int i=max(0, 31-x); i<=30; i++) val[i] = 0;
    }
};

struct segTree{
    Node tree[400002];
    ll lazy[400002];

    void init(int i, int l, int r, ll *A){
        if(l==r){
            tree[i] = Node(A[l]);
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, A);
        init(i*2+1, m+1, r, A);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    void propagate(int i, int l, int r){
        if(!lazy[i]) return;
        tree[i].rotate(lazy[i]);
        if(l!=r) lazy[i*2] += lazy[i], lazy[i*2+1] += lazy[i];
        lazy[i] = 0;
    }

    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].val[0];
        int m = (l+r)>>1;
        return query(i*2, l, m, s, e) + query(i*2+1, m+1, r, s, e);
    }

    void update(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;
        update(i*2, l, m, s, e);
        update(i*2+1, m+1, r, s, e);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    void updateValue(int i, int l, int r, int x, ll v){
        propagate(i, l, r);
        if(l==r){
            tree[i] = Node(v);
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) updateValue(i*2, l, m, x, v), propagate(i*2+1, m+1, r);
        else updateValue(i*2+1, m+1, r, x, v), propagate(i*2, l, m);
        tree[i] = tree[i*2] + tree[i*2+1];
    }
} tree;

int n, q;
ll arr[100002];

void solve_k1();

int main(){
    scanf("%d %d %d", &n, &q, &k);
    for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
    if(k==1) solve_k1();

    tree.init(1, 1, n, arr);
    while(q--){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        if(a==1) tree.updateValue(1, 1, n, b, c);
        else if(a==2) tree.update(1, 1, n, b, c);
        else printf("%lld\n", tree.query(1, 1, n, b, c));
    }
}

struct Fenwick{
    int n;
    ll tree[100002];

    void init(int _n){
        n=_n;
        for(int i=1; i<=n; i++) tree[i] = 0;
    }

    void add(int x, ll y){
        while(x<=n){
            tree[x] += y;
            x += x&-x;
        }
    }

    ll sum(int x){
        ll ret = 0;
        while(x){
            ret += tree[x];
            x-=x&-x;
        }
        return ret;
    }

    ll sum(int l, int r){
        return sum(r) - sum(l-1);
    }
} fenwick;

void solve_k1(){
    fenwick.init(n);
    for(int i=1; i<=n; i++) fenwick.add(i, arr[i]);
    while(q--){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        if(a==1){
            fenwick.add(b, c-arr[b]);
            arr[b]=c;
        }
        else if(a==3){
            printf("%lld\n", fenwick.sum(b, c));
        }
    }
    exit(0);
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:92:19: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'll*' {aka 'long long int*'} [-Wformat=]
   92 |     scanf("%d %d %d", &n, &q, &k);
      |                  ~^           ~~
      |                   |           |
      |                   int*        ll* {aka long long int*}
      |                  %lld
sterilizing.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     scanf("%d %d %d", &n, &q, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:93:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |     for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~
sterilizing.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         scanf("%d %d %d", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp: In function 'void solve_k1()':
sterilizing.cpp:141:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         scanf("%d %d %d", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 1364 KB Output is correct
4 Correct 5 ms 1364 KB Output is correct
5 Correct 7 ms 2388 KB Output is correct
6 Correct 7 ms 2388 KB Output is correct
7 Correct 10 ms 2388 KB Output is correct
8 Correct 10 ms 2388 KB Output is correct
9 Correct 10 ms 2408 KB Output is correct
10 Correct 10 ms 2388 KB Output is correct
11 Correct 7 ms 2388 KB Output is correct
12 Correct 10 ms 2388 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1400 KB Output is correct
2 Correct 31 ms 1340 KB Output is correct
3 Correct 31 ms 1776 KB Output is correct
4 Correct 49 ms 2188 KB Output is correct
5 Correct 48 ms 2316 KB Output is correct
6 Correct 47 ms 2252 KB Output is correct
7 Correct 44 ms 2252 KB Output is correct
8 Correct 42 ms 2284 KB Output is correct
9 Correct 43 ms 2332 KB Output is correct
10 Correct 44 ms 2300 KB Output is correct
11 Correct 42 ms 2304 KB Output is correct
12 Correct 44 ms 2232 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 4488 KB Output is correct
2 Correct 66 ms 33492 KB Output is correct
3 Correct 95 ms 33512 KB Output is correct
4 Correct 247 ms 16924 KB Output is correct
5 Correct 438 ms 66800 KB Output is correct
6 Correct 401 ms 66932 KB Output is correct
7 Correct 55 ms 1988 KB Output is correct
8 Correct 457 ms 66752 KB Output is correct
9 Correct 284 ms 66772 KB Output is correct
10 Correct 300 ms 66780 KB Output is correct
11 Correct 327 ms 66784 KB Output is correct
12 Correct 314 ms 66796 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 33724 KB Output is correct
2 Correct 285 ms 33684 KB Output is correct
3 Correct 178 ms 33608 KB Output is correct
4 Correct 324 ms 17160 KB Output is correct
5 Correct 419 ms 67020 KB Output is correct
6 Correct 463 ms 67032 KB Output is correct
7 Correct 409 ms 66936 KB Output is correct
8 Correct 393 ms 67048 KB Output is correct
9 Correct 288 ms 67060 KB Output is correct
10 Correct 310 ms 66996 KB Output is correct
11 Correct 286 ms 66980 KB Output is correct
12 Correct 360 ms 67032 KB Output is correct