Submission #1296376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296376		rexdino	Sterilizing Spray (JOI15_sterilizing)	C++20	100 / 100	117 ms	6904 KiB

sterilizing

#include <bits/stdc++.h>
#define fi first
#define se second
#define FOR(i,a,b) for (int i=(a); i<=(b); ++i)
#define REP(i,a,b) for (int i=(a); i>=(b); --i)
#define ALL(v) (v).begin(),(v).end()
#define umax(x, y) x = max(x, (y))
#define umin(x, y) x = min(x, (y))
#define el cout << "\n"

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const ll INF = 1e18;


/// CODE ///
int n, q, k, c[N];
set<int> s;
ll t[N];

void upd(int x, int val){
    for (; x <= n; x += (x & -x)) t[x] += val;
}

ll get(int x){
    ll res = 0;
    for (;x > 0; x -= (x & -x)) res += t[x];
    return res;
}


void solve(){
    cin >> n >> q >> k;
    FOR(i, 1, n){
        cin >> c[i];
        if (c[i] != 0) s.insert(i);
        upd(i, c[i]);
    }

    FOR(i, 1, q){
        int type, u, v;
        cin >> type >> u >> v;

        if (type == 1){
            upd(u, v - c[u]);
            c[u] = v;
            s.insert(u);
        } else if (type == 2){
            if(k == 1) continue;
            auto it = s.lower_bound(u);
            vector<int> node;
            while(it != s.end()){
                int pos = *it;
                if (pos > v) break;

                upd(pos, c[pos] / k - c[pos]);
                c[pos] /= k;
                if (c[pos] == 0) node.push_back(pos);

                it++;
            }

            for (int x : node) s.erase(x);

        } else {
            // cout << type << " " << u << " " << v << ": ";
            cout << get(v) - get(u - 1), el;
        }

    }

}


int main(){
    #define NAME "gray"
    if (fopen(NAME".inp", "r")){ 
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();

    return 0;
}

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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