oj.uz

Submission #528932

# Submission time Handle Problem Language Result Execution time Memory
528932 2022-02-21T19:01:46 Z Tadiorn Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 679 ms 10108 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, n, 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, n, l, r);
            if(r > 0) indeksi.insert(l);
                /*for(auto x : indeksi) cout << x << ", ";
                cout << endl;*/
        }
        else if(s == 2){
            if(k != 1){
                //cout << "START" << endl;
                for(auto it = indeksi.lower_bound(l); it != indeksi.end() && !indeksi.empty() && *it <= r; it++){
                //    cout << *it << ": ";
                    update2(1, 1, n, *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, n, l, r) << endl;
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 2 ms 284 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 9 ms 420 KB Output is correct
5 Correct 11 ms 588 KB Output is correct
6 Correct 8 ms 588 KB Output is correct
7 Correct 9 ms 596 KB Output is correct
8 Correct 9 ms 588 KB Output is correct
9 Correct 11 ms 528 KB Output is correct
10 Correct 9 ms 532 KB Output is correct
11 Correct 9 ms 596 KB Output is correct
12 Correct 9 ms 596 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 5152 KB Output is correct
2 Correct 92 ms 4960 KB Output is correct
3 Correct 85 ms 7908 KB Output is correct
4 Correct 154 ms 9460 KB Output is correct
5 Correct 131 ms 10108 KB Output is correct
6 Correct 154 ms 9984 KB Output is correct
7 Correct 139 ms 9960 KB Output is correct
8 Correct 141 ms 10084 KB Output is correct
9 Correct 136 ms 9776 KB Output is correct
10 Correct 138 ms 10016 KB Output is correct
11 Correct 136 ms 9760 KB Output is correct
12 Correct 125 ms 9856 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 776 KB Output is correct
2 Correct 36 ms 3508 KB Output is correct
3 Correct 44 ms 3532 KB Output is correct
4 Correct 95 ms 1996 KB Output is correct
5 Correct 143 ms 7364 KB Output is correct
6 Correct 136 ms 7168 KB Output is correct
7 Correct 114 ms 8644 KB Output is correct
8 Correct 160 ms 8628 KB Output is correct
9 Correct 129 ms 8892 KB Output is correct
10 Correct 134 ms 8900 KB Output is correct
11 Correct 141 ms 8904 KB Output is correct
12 Correct 130 ms 8868 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 3892 KB Output is correct
2 Correct 185 ms 3960 KB Output is correct
3 Correct 330 ms 3572 KB Output is correct
4 Correct 217 ms 4200 KB Output is correct
5 Correct 375 ms 9816 KB Output is correct
6 Correct 377 ms 9752 KB Output is correct
7 Correct 341 ms 9748 KB Output is correct
8 Correct 483 ms 9860 KB Output is correct
9 Correct 417 ms 10108 KB Output is correct
10 Correct 478 ms 10064 KB Output is correct
11 Correct 331 ms 10060 KB Output is correct
12 Correct 679 ms 9920 KB Output is correct