제출 #853699

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
853699		octane	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	226 ms	212448 KiB

sterilizing

#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);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75