oj.uz

Submission #955543

# Submission time Handle Problem Language Result Execution time Memory
955543 2024-03-30T22:30:55 Z AliMark71 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 1176 ms 14752 KB 
//
//  main.cpp
//  GeneralCompetitiveProgramming
//
//  Created by Ali AlSalman on 12/07/2023.
//

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <optional>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <cmath>
#include <climits>

#define endl '\n'

using namespace std;


class SegmentTree {
private:
    int _offset, _back, _sth;
    vector<long long> _data;
    set<int> _non_zero;
    
    long long _query(int v, int qlo, int qhi, int lo, int hi) {
        if (qlo <= lo && hi <= qhi) return _data[v];
        else if (hi <= qlo || qhi <= lo) return 0;
        else {
            int mid = (lo + hi) >> 1;
            return _query(v * 2,     qlo, qhi, lo, mid) +
                   _query(v * 2 + 1, qlo, qhi, mid, hi);
        }
    }
    
    void _log_update(int v) {
        for (v >>= 1; 1 <= v; v >>= 1) {
            _data[v] = _data[v * 2] + _data[v * 2 + 1];
        }
    }
    
public:
    SegmentTree(unsigned int n, int strength) : _offset(1) {
        if (__builtin_popcount(n) == 1) _offset = n;
        else _offset = 1<<((sizeof(unsigned int) * 8) - __builtin_clz(n));
        
        _data = vector<long long>(_offset * 2);
        _back = _offset;
        _sth = strength;
    };
    
    void push_back(long long val) {
        if (val) _non_zero.insert(_back);
        _data[_back] = val;
        _log_update(_back++);
    }
    
    void set_at(int ind, long long val) {
        ind += _offset;
        
        if (val) _non_zero.insert(ind);
        else _non_zero.erase(ind);
        _data[ind] = val;
        _log_update(ind);
    }
    
    void spray(int low, int hi) {
        if (_sth == 1) return;
        
        set<int> _non_zero_copy(_non_zero.begin(), _non_zero.end());
        auto low_it = _non_zero.lower_bound(low + _offset), hi_it = _non_zero.lower_bound(hi + _offset);
        for (auto it = low_it; it != hi_it; it = next(it)) {
            _data[*it] /= _sth;
            if (_data[*it] == 0) _non_zero_copy.erase(*it);
            _log_update(*it);
        }
        
        _non_zero = std::move(_non_zero_copy);
    }
    
    long long query(int query_low, int query_hi) {
        query_low += _offset; query_hi += _offset;
        return _query(1, query_low, query_hi, _offset, _offset * 2);
    }
};

istream& operator>>(istream &in, SegmentTree &tree) {
    long long _t; in>>_t;
    tree.push_back(_t);
    return in;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    
    
    int n, q, k;
    cin>>n>>q>>k;
    
    SegmentTree tree(n, k);
    while (n--) cin>>tree;
    
    while (q--) {
        int t;
        cin>>t;
        if (t == 1) {
            int i, val;
            cin>>i>>val;
            tree.set_at(--i, (long long) val);
        } else if (t == 2) {
            int l, r;
            cin>>l>>r;
            tree.spray(--l, r);
        } else {
            int l, r;
            cin>>l>>r;
            cout<<tree.query(--l, r)<<endl;
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 15 ms 600 KB Output is correct
5 Correct 17 ms 864 KB Output is correct
6 Correct 12 ms 860 KB Output is correct
7 Correct 16 ms 872 KB Output is correct
8 Correct 16 ms 880 KB Output is correct
9 Correct 21 ms 864 KB Output is correct
10 Correct 13 ms 860 KB Output is correct
11 Correct 14 ms 856 KB Output is correct
12 Correct 19 ms 860 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 5916 KB Output is correct
2 Correct 39 ms 4948 KB Output is correct
3 Correct 46 ms 7852 KB Output is correct
4 Correct 62 ms 9444 KB Output is correct
5 Correct 65 ms 10128 KB Output is correct
6 Correct 67 ms 10064 KB Output is correct
7 Correct 82 ms 9932 KB Output is correct
8 Correct 66 ms 9880 KB Output is correct
9 Correct 64 ms 9880 KB Output is correct
10 Correct 63 ms 9812 KB Output is correct
11 Correct 66 ms 9804 KB Output is correct
12 Correct 63 ms 9904 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1276 KB Output is correct
2 Correct 25 ms 3820 KB Output is correct
3 Correct 29 ms 3928 KB Output is correct
4 Correct 51 ms 3176 KB Output is correct
5 Correct 95 ms 8600 KB Output is correct
6 Correct 91 ms 8608 KB Output is correct
7 Correct 51 ms 6228 KB Output is correct
8 Correct 82 ms 8528 KB Output is correct
9 Correct 52 ms 8532 KB Output is correct
10 Correct 52 ms 8704 KB Output is correct
11 Correct 51 ms 8276 KB Output is correct
12 Correct 50 ms 8528 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 7764 KB Output is correct
2 Correct 341 ms 8184 KB Output is correct
3 Correct 700 ms 7252 KB Output is correct
4 Correct 391 ms 5712 KB Output is correct
5 Correct 663 ms 14412 KB Output is correct
6 Correct 782 ms 14560 KB Output is correct
7 Correct 548 ms 14752 KB Output is correct
8 Correct 1176 ms 14480 KB Output is correct
9 Correct 204 ms 14416 KB Output is correct
10 Correct 268 ms 14312 KB Output is correct
11 Correct 174 ms 14312 KB Output is correct
12 Correct 403 ms 14520 KB Output is correct