oj.uz

Submission #203342

# Submission time Handle Problem Language Result Execution time Memory
203342 2020-02-20T09:14:26 Z nvmdava Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 186 ms 9592 KB 
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define ff first
#define ss second
#define N 100005
#define MOD 1000000007
#define INF 0x3f3f3f3f

ll bit[N];
ll query(int x){
    ll w = 0;
    while(x){
        w += bit[x];
        x -= x & -x;
    }
    return w;
}
void update(int x, ll w){
    while(x < N){
        bit[x] += w;
        x += x & -x;
    }
}
set<int> in;
ll a[N];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, q, k;
    cin>>n>>q>>k;
    for(int i = 1; i <= n; ++i){
        cin>>a[i];
        update(i, a[i]);
        if(a[i])
            in.insert(i);
    }

    while(q--){
        int t, l, r;
        cin>>t>>l>>r;
        if(t == 3)
            cout<<query(r) - query(l - 1)<<'\n';
        else if(t == 1){
            update(l, r - a[l]);
            if(a[l] && !r)
                in.erase(l);
            else if(!a[l] && r)
                in.insert(l);
            a[l] = r;
        } else {
            if(k == 1) continue;
            auto it = in.lower_bound(l);
            while(it != in.end() && *it <= r){
                auto f = it++;
                update(*f, a[*f] / k - a[*f]);
                a[*f] /= k;
                if(a[*f] == 0)
                    in.erase(f);
            }
        }
    }

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 9 ms 504 KB Output is correct
5 Correct 9 ms 632 KB Output is correct
6 Correct 8 ms 632 KB Output is correct
7 Correct 9 ms 632 KB Output is correct
8 Correct 9 ms 632 KB Output is correct
9 Correct 10 ms 760 KB Output is correct
10 Correct 10 ms 632 KB Output is correct
11 Correct 8 ms 632 KB Output is correct
12 Correct 9 ms 760 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 5752 KB Output is correct
2 Correct 52 ms 4472 KB Output is correct
3 Correct 58 ms 7288 KB Output is correct
4 Correct 75 ms 9128 KB Output is correct
5 Correct 80 ms 9592 KB Output is correct
6 Correct 77 ms 9592 KB Output is correct
7 Correct 83 ms 9592 KB Output is correct
8 Correct 79 ms 9592 KB Output is correct
9 Correct 77 ms 9464 KB Output is correct
10 Correct 76 ms 9464 KB Output is correct
11 Correct 83 ms 9384 KB Output is correct
12 Correct 79 ms 9568 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1144 KB Output is correct
2 Correct 20 ms 2424 KB Output is correct
3 Correct 23 ms 2552 KB Output is correct
4 Correct 44 ms 2552 KB Output is correct
5 Correct 65 ms 5756 KB Output is correct
6 Correct 63 ms 5752 KB Output is correct
7 Correct 66 ms 5880 KB Output is correct
8 Correct 63 ms 5784 KB Output is correct
9 Correct 59 ms 5624 KB Output is correct
10 Correct 59 ms 5624 KB Output is correct
11 Correct 58 ms 5624 KB Output is correct
12 Correct 57 ms 5528 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 5344 KB Output is correct
2 Correct 82 ms 5496 KB Output is correct
3 Correct 92 ms 4480 KB Output is correct
4 Correct 87 ms 4344 KB Output is correct
5 Correct 124 ms 9336 KB Output is correct
6 Correct 139 ms 9336 KB Output is correct
7 Correct 118 ms 9336 KB Output is correct
8 Correct 155 ms 9336 KB Output is correct
9 Correct 141 ms 9336 KB Output is correct
10 Correct 148 ms 9216 KB Output is correct
11 Correct 124 ms 9208 KB Output is correct
12 Correct 186 ms 9208 KB Output is correct