oj.uz

Submission #528929

# Submission time Handle Problem Language Result Execution time Memory
528929 2022-02-21T18:55:06 Z Tadiorn Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 5000 ms 7636 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<int,int>
#define pll pair<long long,long long>
#define INF 1000000000
#define LINF 1000000000000000000
#define pb push_back
#define MAXN 100010
using namespace std;

ll seg[4*MAXN];
set<int> indeksi;
void update(int node, int l, int r, int idx, int val){
    if(l == r){
        seg[node] = val;
        //cout << "idx: " << l << ", val: " << seg[node] << ", node: " << node << endl;
        return;
    }
    int mid = (l+r)/2;
    if(idx <= mid) update(2*node, l, mid, idx, val);
    else update(2*node+1, mid+1, r, idx, val);
    seg[node] = seg[2*node] + seg[2*node+1];
}
vector<int> rem;
void update2(int node, int l, int r, int idx, int k){
    if(l == r){
            //cout << "indeks: " << l << ": " << seg[node] << endl;
        seg[node] /= k;
        if(seg[node] == 0){ /*cout << "brise se indeks: " << l << ", jer je seg[node] = " << seg[node] << ", node: " << node << endl;*/ rem.push_back(idx);}
        return;
    }
    int mid = (l+r)/2;
    if(idx <= mid) update2(2*node, l, mid, idx, k);
    else update2(2*node+1, mid+1, r, idx, k);
    seg[node] = seg[2*node] + seg[2*node+1];
}
ll query(int node, int l, int r, int L, int R){
    if(L <= l && r <= R)
        return seg[node];
    int mid = (l+r)/2;
    ll sum = 0;
    if(L <= mid) sum += query(2*node, l, mid, L, R);
    if(R > mid) sum += query(2*node+1, mid+1, r, L, R);
    return sum;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, q, k;
    cin >> n >> q >> k;
    for(int i = 0; i < n; i++){
        int t; cin >> t;
        update(1, 1, MAXN, i+1, t);
    }
    for(int i = 1; i <= n; i++) indeksi.insert(i);
    for(int i = 0; i < q; i++){
        int s, l, r;
        cin >> s >> l >> r;
        if(s == 1){
            update(1, 1, MAXN, l, r);
            if(r > 0) indeksi.insert(l);
                /*for(auto x : indeksi) cout << x << ", ";
                cout << endl;*/
        }
        else if(s == 2){
            if(k != 2){
                //cout << "START" << endl;
                for(auto it = indeksi.lower_bound(l); it != indeksi.end() && !indeksi.empty() && *it <= r; it++){
                //    cout << *it << ": ";
                    update2(1, 1, MAXN, *it, k);
                //    cout << "done" << endl;
                }
                //cout << "MID" << endl;
                for(auto x : rem){
                    indeksi.erase(x);
                } rem.clear();
                /*for(auto x : indeksi) cout << x << ", ";
                cout << endl;*/
                //cout << "END" << endl;
            }
        }
        else{
            cout << query(1, 1, MAXN, l, r) << endl;
        }
    }
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 10 ms 332 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Incorrect 3 ms 468 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5078 ms 4040 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 964 KB Output is correct
2 Correct 40 ms 3660 KB Output is correct
3 Correct 44 ms 3676 KB Output is correct
4 Correct 89 ms 2432 KB Output is correct
5 Correct 139 ms 7636 KB Output is correct
6 Incorrect 113 ms 7472 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 4160 KB Output is correct
2 Correct 211 ms 4316 KB Output is correct
3 Incorrect 56 ms 3828 KB Output isn't correct
4 Halted 0 ms 0 KB -