oj.uz

Submission #400195

# Submission time Handle Problem Language Result Execution time Memory
400195 2021-05-07T14:32:20 Z SavicS Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 179 ms 8900 KB 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 100005;
const int inf = 1e9 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n, q, K;
int niz[maxn];

ll dud[maxn];
void upd(int x, ll val){
    while(x <= maxn){
        dud[x] += val;
        x += x&(-x);
    }
}
ll query(int x){
    ll sum = 0;
    while(x > 0){
        sum += dud[x];
        x -= x&(-x);
    }
    return sum;
}

void add(int pos, ll val){
    upd(pos, val - niz[pos]);
    niz[pos] = val;
}

int main()
{
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
    cin >> n >> q >> K;
    ff(i,1,n)cin >> niz[i];

    set<int> s;
    ff(i,1,n)upd(i, niz[i]), s.insert(i);

    while(q--){
        int t;
        cin >> t;

        if(t == 1){
            int pos, val;
            cin >> pos >> val;
            add(pos, val);
            s.insert(pos);
        }

        if(t == 2){
            int l, r;
            cin >> l >> r;
            if(K == 1)continue;

            auto A = s.lower_bound(l);
            auto B = s.upper_bound(r);
            while(A != B){
                add(*A, niz[*A] / K);
                if(niz[*A] == 0)s.erase(A++);
                else A++;
            }
        }

        if(t == 3){
            int l, r;
            cin >> l >> r;
            cout << query(r) - query(l - 1) << '\n';
        }

    }

    return 0;
}
/**

5 10 3
1 2 8 1 3
1 2 5
2 3 5
3 2 5
2 1 4
1 3 2
3 3 5
1 2 4
2 1 2
1 1 4
3 1 5

// probati bojenje sahovski ili slicno

**/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 428 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Correct 5 ms 588 KB Output is correct
6 Correct 4 ms 588 KB Output is correct
7 Correct 5 ms 592 KB Output is correct
8 Correct 5 ms 592 KB Output is correct
9 Correct 5 ms 596 KB Output is correct
10 Correct 5 ms 592 KB Output is correct
11 Correct 5 ms 588 KB Output is correct
12 Correct 5 ms 600 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 3772 KB Output is correct
2 Correct 47 ms 2756 KB Output is correct
3 Correct 56 ms 5204 KB Output is correct
4 Correct 71 ms 6500 KB Output is correct
5 Correct 83 ms 6680 KB Output is correct
6 Correct 81 ms 6600 KB Output is correct
7 Correct 80 ms 6700 KB Output is correct
8 Correct 83 ms 6724 KB Output is correct
9 Correct 79 ms 6788 KB Output is correct
10 Correct 82 ms 6676 KB Output is correct
11 Correct 78 ms 6724 KB Output is correct
12 Correct 78 ms 6624 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 796 KB Output is correct
2 Correct 22 ms 3348 KB Output is correct
3 Correct 25 ms 3348 KB Output is correct
4 Correct 44 ms 3052 KB Output is correct
5 Correct 75 ms 7664 KB Output is correct
6 Correct 72 ms 7620 KB Output is correct
7 Correct 72 ms 7756 KB Output is correct
8 Correct 77 ms 7568 KB Output is correct
9 Correct 69 ms 7440 KB Output is correct
10 Correct 67 ms 7492 KB Output is correct
11 Correct 68 ms 7432 KB Output is correct
12 Correct 66 ms 7408 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 3552 KB Output is correct
2 Correct 74 ms 5184 KB Output is correct
3 Correct 89 ms 4232 KB Output is correct
4 Correct 84 ms 4164 KB Output is correct
5 Correct 116 ms 8900 KB Output is correct
6 Correct 130 ms 8900 KB Output is correct
7 Correct 114 ms 8884 KB Output is correct
8 Correct 150 ms 8876 KB Output is correct
9 Correct 125 ms 8772 KB Output is correct
10 Correct 139 ms 8696 KB Output is correct
11 Correct 112 ms 8772 KB Output is correct
12 Correct 179 ms 8804 KB Output is correct