oj.uz

Submission #48577

# Submission time Handle Problem Language Result Execution time Memory
48577 2018-05-16T17:56:57 Z MladenP Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 313 ms 8944 KB 
#include<bits/stdc++.h>
#define STIZE(x) fprintf(stderr, "STIZE%d\n", x);
#define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x);
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define mid (l+r)/2
#define endl '\n'
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 1000000000000000LL
#define INF 1000000000
#define EPS 1e-9
using namespace std;
#define MAXN 100010
set<int> s;
vector<int> izbaciti;
lld bit[MAXN], a[MAXN];
lld query(int idx) {
    lld rez = 0;
    for( ; idx > 0; idx -= idx&-idx) rez += bit[idx];
    return rez;
}
void update(int idx, lld val) {
    val -= a[idx]; a[idx] += val;
    for( ; idx < MAXN; idx += idx&-idx) bit[idx] += val;
}
int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    lld N, Q, K, a1; cin >> N >> Q >> K;
    for(int i = 1; i <= N; i++) {
        cin >> a1; update(i, a1);
        if(a[i] != 0) s.insert(i);
    }
    while(Q--) {
        int type, u1, u2; cin >> type >> u1 >> u2;
        if(type == 1) {
            update(u1, u2);
            if(u2 != 0) s.insert(u1);
            else s.erase(u1);
        } else if(type == 2) {
            if(K == 1) continue;
            for(auto it = s.lower_bound(u1); it != s.end() && *it <= u2; it++) {
                update(*it, a[*it]/K);
                if(a[*it] == 0) izbaciti.pb(*it);
            }
            for(auto x : izbaciti) s.erase(x);
            izbaciti.clear();
        } else {
            cout << query(u2) - query(u1-1) << endl;
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 3 ms 568 KB Output is correct
4 Correct 6 ms 568 KB Output is correct
5 Correct 7 ms 824 KB Output is correct
6 Correct 6 ms 856 KB Output is correct
7 Correct 6 ms 856 KB Output is correct
8 Correct 7 ms 856 KB Output is correct
9 Correct 8 ms 856 KB Output is correct
10 Correct 6 ms 856 KB Output is correct
11 Correct 6 ms 856 KB Output is correct
12 Correct 6 ms 856 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 5232 KB Output is correct
2 Correct 58 ms 5232 KB Output is correct
3 Correct 67 ms 6868 KB Output is correct
4 Correct 91 ms 8444 KB Output is correct
5 Correct 112 ms 8728 KB Output is correct
6 Correct 111 ms 8728 KB Output is correct
7 Correct 110 ms 8728 KB Output is correct
8 Correct 116 ms 8728 KB Output is correct
9 Correct 108 ms 8728 KB Output is correct
10 Correct 123 ms 8728 KB Output is correct
11 Correct 97 ms 8728 KB Output is correct
12 Correct 104 ms 8728 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8728 KB Output is correct
2 Correct 19 ms 8728 KB Output is correct
3 Correct 26 ms 8728 KB Output is correct
4 Correct 46 ms 8728 KB Output is correct
5 Correct 71 ms 8728 KB Output is correct
6 Correct 72 ms 8728 KB Output is correct
7 Correct 73 ms 8728 KB Output is correct
8 Correct 67 ms 8728 KB Output is correct
9 Correct 64 ms 8728 KB Output is correct
10 Correct 63 ms 8728 KB Output is correct
11 Correct 64 ms 8728 KB Output is correct
12 Correct 64 ms 8728 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 8728 KB Output is correct
2 Correct 98 ms 8728 KB Output is correct
3 Correct 125 ms 8728 KB Output is correct
4 Correct 101 ms 8728 KB Output is correct
5 Correct 166 ms 8728 KB Output is correct
6 Correct 181 ms 8728 KB Output is correct
7 Correct 151 ms 8728 KB Output is correct
8 Correct 221 ms 8728 KB Output is correct
9 Correct 181 ms 8820 KB Output is correct
10 Correct 219 ms 8840 KB Output is correct
11 Correct 161 ms 8840 KB Output is correct
12 Correct 313 ms 8944 KB Output is correct