제출 #1120113

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1120113		thefless	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	507 ms	77736 KiB

sterilizing

#include<bits/stdc++.h>
using namespace std;
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define fi first
#define base 31
#define sz(x) (int)(x).size()
#define se second
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define name "name"

const int oo = 1e9 + 7;
const ll loo = (ll)1e18 + 7;
const int MOD = 1e9 + 7;
const int N = 2e5 + 3;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}

int n , q , k;
int a[N];
struct SEGTREE{
    int lazy[N << 2];
    vector<ll> st[N << 2];
    void build(int id , int l , int r){
         st[id].assign(33 , 0);
        if(l == r){
            st[id][30] = a[l];
            for(int i = 29 ; i >= 0 ; i--) st[id][i] = st[id][i + 1] / k;
            return;
        }
        int mid = l + r >> 1;
        build(id << 1 , l , mid);
        build(id << 1 | 1 , mid + 1 , r);
        for(int i = 0 ; i <= 30 ; i++) st[id][i] = st[id << 1][i] + st[id << 1 | 1][i];
    }
    void down(int id , int l , int r){
        int val = lazy[id];
        if(val == 0) return;
        lazy[id] = 0;
        minimize(val, 30);
        for(int i = 30 ; i >= val ; i--){
            st[id << 1][i] = st[id << 1][i - val];
            st[id << 1 | 1][i] = st[id << 1 | 1][i - val];
        }
        for(int i = val - 1 ; i >= 0 ; i--){
            st[id << 1][i] = st[id << 1][i + 1] / k;
            st[id << 1 | 1][i] = st[id << 1 | 1][i + 1] / k;
        }
        lazy[id << 1] += val;
        lazy[id << 1 | 1] += val;
    }
    void update1(int id , int l , int r , int t , int v){
        if(l > t || r < t) return;
        if(l == r){
            st[id][30] = v;
            for(int i = 29 ; i >= 0 ; i--) st[id][i] = st[id][i + 1] / k;
            return;
        }
        int mid = l + r >> 1;
        down(id , l , r);
        update1(id << 1 , l , mid , t , v);
        update1(id << 1 | 1 , mid + 1 , r , t , v);
        for(int i = 0 ; i <= 30 ; i++) st[id][i] = st[id << 1][i] + st[id << 1 | 1][i];
    }
    void update(int id , int l , int r , int u , int v){
        if(l > v || r < u) return;
        if(u <= l && r <= v){
            for(int i = 30 ; i > 0 ; i--) st[id][i] = st[id][i - 1];
            st[id][0] = st[id][1] / k;
            lazy[id]++;
            return;
        }
        int mid = l + r >> 1;
        down(id , l , r);
        update(id << 1 , l , mid , u , v);
        update(id << 1 | 1 , mid + 1 , r , u , v);
        for(int i = 0 ; i <= 30 ; i++) st[id][i] = st[id << 1][i] + st[id << 1 | 1][i];
    }
    ll get(int id , int l , int r , int u , int v){
        if(l > v || r < u) return 0;
        if(u <= l && r <= v) return st[id][30];
        int mid = l + r >> 1;
        down(id , l , r);
        return get(id << 1 , l , mid , u , v) + get(id << 1 | 1 , mid + 1 , r , u , v);
    }
}segtree;

void input(){
    cin >> n >> q >> k;
    for(int i = 1 ; i <= n ; i++) cin >> a[i];
    segtree.build(1 , 1 , n);
}
void solve(){
    while(q--){
        int type;
        cin >> type;
        if(type == 1){
            int i , x;
            cin >> i >> x;
            segtree.update1(1 , 1 , n , i , x);
        }
        if(type == 2){
            int l , r;
            cin >> l >> r;
            segtree.update(1 , 1 , n , l , r);
        }
        if(type == 3){
            int l , r;
            cin >> l >> r;
            cout << segtree.get(1 , 1 , n , l , r) << '\n';
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    if (fopen(name".inp", "r")){
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }
    input();
    solve();
}
// author: thefless

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

sterilizing.cpp: In member function 'void SEGTREE::build(int, int, int)':
sterilizing.cpp:35:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         int mid = l + r >> 1;
      |                   ~~^~~
sterilizing.cpp: In member function 'void SEGTREE::update1(int, int, int, int, int)':
sterilizing.cpp:63:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |         int mid = l + r >> 1;
      |                   ~~^~~
sterilizing.cpp: In member function 'void SEGTREE::update(int, int, int, int, int)':
sterilizing.cpp:77:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |         int mid = l + r >> 1;
      |                   ~~^~~
sterilizing.cpp: In member function 'long long int SEGTREE::get(int, int, int, int, int)':
sterilizing.cpp:86:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |         int mid = l + r >> 1;
      |                   ~~^~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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