oj.uz

Submission #400194

# Submission time Handle Problem Language Result Execution time Memory
400194 2021-05-07T14:30:29 Z SavicS Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 69 ms 9200 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);
        }

        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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 5468 KB Output is correct
2 Correct 43 ms 4292 KB Output is correct
3 Correct 47 ms 6832 KB Output is correct
4 Correct 59 ms 8516 KB Output is correct
5 Correct 67 ms 9068 KB Output is correct
6 Correct 67 ms 9028 KB Output is correct
7 Correct 69 ms 9200 KB Output is correct
8 Correct 67 ms 9064 KB Output is correct
9 Correct 67 ms 8940 KB Output is correct
10 Correct 66 ms 8860 KB Output is correct
11 Correct 66 ms 8908 KB Output is correct
12 Correct 66 ms 8996 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 1228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 5128 KB Output isn't correct
2 Halted 0 ms 0 KB -