Submission #153112

#	Time	Username	Problem	Language	Result	Execution time	Memory
153112		karma	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	242 ms	9184 KiB

sterilizing

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define ll      long long
#define pb      emplace_back

using namespace std;

const int N = int(1e5) + 2;

int n, q, k, a[N], irene, cmd, x, y;
ll t[N];
set<int> s;
vector<int> rmv;

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

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if(fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    cin >> n >> q >> k;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i]; Update(i, a[i]);
        if(a[i]) s.insert(i);
    }
    rmv.clear();
    while(q --) {
        cin >> cmd >> x >> y;
        if(cmd == 1) {
            if(y && !a[x]) s.insert(x);
            Update(x, y - a[x]); a[x] = y;
        } else if(cmd == 2) {
           if(k == 1) continue;
           auto ptr = s.lower_bound(x);
           while(*ptr >= x && *ptr <= y && ptr != s.end()) {
               irene = a[*ptr] / k;
               Update(*ptr, irene - a[*ptr]);
               if(!irene) rmv.pb(*ptr);
               a[*ptr] = irene, ptr = next(ptr);
           }
           while(rmv.size()) s.erase(rmv.back()), rmv.pop_back();
        } else cout << Query(y) - Query(x - 1) << '\n';
    }
}

Compilation message (stderr)

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

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