Submission #776387

#	Time	Username	Problem	Language	Result	Execution time	Memory
776387		ar_paixaos19	Sterilizing Spray (JOI15_sterilizing)	C++14	0 / 100	240 ms	33748 KiB

sterilizing

#include <bits/stdc++.h>
#define ser stderr
typedef long long ll;
using namespace std;

const int MAXN = 100010;
const int MAXL = 31;

int n, q;
ll k;
ll seg[4 * MAXN][MAXL];
int lz[4 * MAXN];

void refresh(int pos, int ini, int fim){
    if(lz[pos] == 0) return;

    int m = (ini + fim) / 2;
    int e = 2 * pos, d = 2 * pos + 1;

    lz[e] += lz[pos], lz[d] += lz[pos];
    int l = lz[pos];
    lz[pos] = 0;

    for(int i = 0; i < MAXL; i++){
        seg[pos][i] = seg[pos][i + l];
    }

    return;
}

void merge(int pos, int ini, int fim){
    int m = (ini + fim) / 2;
    int e = 2 * pos, d = 2 * pos + 1;

    for(int i = 0; i < MAXL; i++){
        seg[pos][i] = seg[e][i] + seg[d][i];
    }

    return;
}

void update1(int pos, int ini, int fim, int id, ll val){
    refresh(pos, ini, fim);
    if(id < ini || id > fim) return;
    if(ini == fim){
        for(int i = 0; i < MAXL; i++){
            seg[pos][i] = val;
            val /= k;
        }
        return;
    }

    int m = (ini + fim) / 2;
    int e = 2 * pos, d = 2 * pos + 1;

    update1(e, ini, m, id, val);
    update1(d, m + 1, fim, id, val);

    merge(pos, ini, fim);
    return;
}

void update2(int pos, int ini, int fim, int l, int r){
    refresh(pos, ini, fim);
    if(l > fim || r < ini) return;
    if(l <= ini && fim <= r){
        lz[pos]++;
        refresh(pos, ini, fim);
        return;
    }

    int m = (ini + fim) / 2;
    int e = 2 * pos, d = 2 * pos + 1;

    update2(e, ini, m, l, r);
    update2(d, m + 1, fim, l, r);

}

ll query(int pos, int ini, int fim, int l, int r){
    if(l > fim || r < ini) return 0;
    refresh(pos, ini, fim);
    if(l <= ini && fim <= r) return seg[pos][0];
    int m = (ini + fim) / 2.;
    int e = 2 * pos, d = 2 * pos + 1;

    return query(e, ini, m, l, r) + query(d, m + 1, fim, l, r);
}

int main(){
    scanf("%d %d %lld", &n, &q, &k);
    
    for(int i = 1; i <= n; i++){
        ll v; scanf("%lld", &v);
        update1(1, 1, n, i, v);
    }

    for(int i = 1; i <= q; i++){
        int type; scanf("%d", &type);
        if(type == 1){
            int a;
            ll b;
            scanf("%d %lld", &a, &b);
            update1(1, 1, n, a, b);
        }
        if(type == 2){
            int l, r; scanf("%d %d", &l, &r);
            update2(1, 1, n, l, r);
        }
        if(type == 3){
            int l, r; scanf("%d %d", &l, &r);
            ll resp = query(1, 1, n, l, r);
            printf("%lld\n", resp);
        }
    }

    return 0;
}

Compilation message (stderr)

sterilizing.cpp: In function 'void refresh(int, int, int)':
sterilizing.cpp:17:9: warning: unused variable 'm' [-Wunused-variable]
   17 |     int m = (ini + fim) / 2;
      |         ^
sterilizing.cpp: In function 'void merge(int, int, int)':
sterilizing.cpp:32:9: warning: unused variable 'm' [-Wunused-variable]
   32 |     int m = (ini + fim) / 2;
      |         ^
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     scanf("%d %d %lld", &n, &q, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:94:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         ll v; scanf("%lld", &v);
      |               ~~~~~^~~~~~~~~~~~
sterilizing.cpp:99:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         int type; scanf("%d", &type);
      |                   ~~~~~^~~~~~~~~~~~~
sterilizing.cpp:103:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |             scanf("%d %lld", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~
sterilizing.cpp:107:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |             int l, r; scanf("%d %d", &l, &r);
      |                       ~~~~~^~~~~~~~~~~~~~~~~
sterilizing.cpp:111:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |             int l, r; scanf("%d %d", &l, &r);
      |                       ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75