Submission #723962

#	Time	Username	Problem	Language	Result	Execution time	Memory
723962		kkts	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	1648 ms	9284 KiB

sterilizing

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t[N], c[N], n;
void upd(int id, int v) {
    for(id; id <= n; id += id & (-id)) t[id] += v;
}
int get(int id) {
    int ans = 0;
    for(id; id >= 1; id -= id & (-id)) ans += t[id];
    return ans;
}
void update(int x, int v) {
    if(c[x] == v) return;
    upd(x, -c[x]);
    c[x] = v;
    upd(x, c[x]);
}
main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int  q, k;
    cin >> n >> q >> k;
    set<int> s;
    for(int i = 1; i <= n; i++) cin >> c[i], upd(i, c[i]), s.insert(i);
    s.insert(n + 5);
    for(int i = 1; i <= q; i++) {
        int t, l, r;
        cin >> t >> l >> r;
        if(t == 1) {
            update(l, r);
            s.insert(l);
            continue;
        }
        if(t == 2) {
            int L = l - 1;
            while(k > 1 && *s.upper_bound(L) <= r) {
                int x = *s.upper_bound(L);
                s.erase(x);
                update(x, c[x] / k);
                if(c[x] / k != c[x]) s.insert(x);
                L = x;
            }
        } else cout << get(r) - get(l - 1) << "\n";
    }
 }

Compilation message (stderr)

sterilizing.cpp: In function 'void upd(long long int, long long int)':
sterilizing.cpp:10:9: warning: statement has no effect [-Wunused-value]
   10 |     for(id; id <= n; id += id & (-id)) t[id] += v;
      |         ^~
sterilizing.cpp: In function 'long long int get(long long int)':
sterilizing.cpp:14:9: warning: statement has no effect [-Wunused-value]
   14 |     for(id; id >= 1; id -= id & (-id)) ans += t[id];
      |         ^~
sterilizing.cpp: At global scope:
sterilizing.cpp:23:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   23 | main(){
      | ^~~~

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