oj.uz

Submission #630169

# Submission time Handle Problem Language Result Execution time Memory
630169 2022-08-15T19:39:13 Z Soul234 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 230 ms 10404 KB 
#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

tcT> bool ckmin(T&a, const T&b) {
    return b < a ? a=b,1 : 0; }
tcT> bool ckmax(T&a, const T&b) {
    return b > a ? a=b,1 : 0; }

const int MOD = 1e9 + 7;

struct SegTree {
    const ll ID = 0; ll comb(ll a, ll b) { return a + b; }
    int N; V<ll> seg;
    void init(int _N) {
        for(N = 1; N < _N; ) N <<= 1;
        seg.assign(N<<1, ID);
    }
    void pull(int p) { seg[p] = comb(seg[p<<1], seg[p<<1|1]); }
    void upd(int p, ll val) {
        seg[p += N] = val;
        for(p >>= 1; p>0; p >>= 1) pull(p);
    }
    ll query(int l, int r) {
        ll ra = 0, rb = 0;
        for(l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
            if(l&1) ra = comb(ra, seg[l++]);
            if(r&1) rb = comb(seg[--r], rb);
        }
        return comb(ra, rb);
    }
};

const int MX = 1e5+5;
int N, Q, K, C[MX];

set<int> idx;
SegTree st;

void solve() {
    cin >> N >> Q >> K;
    st.init(N + 5);
    FOR(i,1,N+1) {
        cin >> C[i];
        st.upd(i, C[i]);
        if(C[i] > 0) idx.insert(i);
    }
    while(Q-- > 0) {
        int t, a, b;
        cin >> t >> a >> b;
        if(t == 1) {
            C[a] = b;
            st.upd(a, b);
            idx.erase(a);
            if(b > 0) idx.insert(a);
        }
        else if(t == 2) {
            if(K == 1) continue;
            auto it = idx.lower_bound(a);
            vi todo;
            for(; it!=idx.end() && *it <= b; it++) {
                int ind = *it;
                st.upd(ind, C[*it] /= K);
                if(C[*it] == 0) todo.pb(ind);
            }
            each(ind, todo) idx.erase(ind);
        }
        else {
            cout << st.query(a, b) << nl;
        }
    }
}

int main() {
    setIO();

    int t=1;
    //cin>>t;
    while(t-->0) {
        solve();
    }

    return 0;
}

Compilation message

sterilizing.cpp: In function 'void setIO(std::string)':
sterilizing.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 4 ms 596 KB Output is correct
12 Correct 4 ms 596 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 6160 KB Output is correct
2 Correct 47 ms 5096 KB Output is correct
3 Correct 54 ms 8268 KB Output is correct
4 Correct 76 ms 9912 KB Output is correct
5 Correct 92 ms 10404 KB Output is correct
6 Correct 78 ms 10400 KB Output is correct
7 Correct 80 ms 10308 KB Output is correct
8 Correct 81 ms 10352 KB Output is correct
9 Correct 83 ms 10260 KB Output is correct
10 Correct 85 ms 10188 KB Output is correct
11 Correct 81 ms 10188 KB Output is correct
12 Correct 83 ms 10188 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1108 KB Output is correct
2 Correct 15 ms 2908 KB Output is correct
3 Correct 19 ms 3004 KB Output is correct
4 Correct 39 ms 2716 KB Output is correct
5 Correct 52 ms 6636 KB Output is correct
6 Correct 53 ms 6588 KB Output is correct
7 Correct 59 ms 6696 KB Output is correct
8 Correct 57 ms 6600 KB Output is correct
9 Correct 52 ms 6508 KB Output is correct
10 Correct 52 ms 6532 KB Output is correct
11 Correct 52 ms 6552 KB Output is correct
12 Correct 50 ms 6524 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 5656 KB Output is correct
2 Correct 80 ms 5848 KB Output is correct
3 Correct 99 ms 4904 KB Output is correct
4 Correct 81 ms 4460 KB Output is correct
5 Correct 125 ms 10188 KB Output is correct
6 Correct 146 ms 10136 KB Output is correct
7 Correct 121 ms 10176 KB Output is correct
8 Correct 180 ms 10196 KB Output is correct
9 Correct 149 ms 10144 KB Output is correct
10 Correct 171 ms 10212 KB Output is correct
11 Correct 134 ms 10200 KB Output is correct
12 Correct 230 ms 10192 KB Output is correct