oj.uz

Submission #750396

# Submission time Handle Problem Language Result Execution time Memory
750396 2023-05-29T13:10:59 Z 7as__7 Sterilizing Spray (JOI15_sterilizing) C++17
0 / 100
 5000 ms 6184 KB 
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define all(x) x.begin(),x.end()
const int sz = 1e6 + 1, mod = 1e9 + 7, inf = -1e18;
int N = 1, l, r;
int seg[(int)3e5 + 1];
void upd(int idx, int x) {
    idx--;
    idx += N;
    seg[idx] = x;
    idx /= 2;
    while (idx) {
        seg[idx] = seg[idx * 2] + seg[idx * 2 + 1];
        idx /= 2;
    }
}
int calc(int s, int e, int i) {
    if (s > r || e < l)return 0;
    if (s >= l && e <= r) {
        return seg[i];
    }
    int md = (s + e) / 2;
    return calc(s, md, i * 2) + calc(md + 1, e, i * 2 + 1);
}
signed main()
{
    int n, q, k;
    cin >> n >> q >> k;
    while (N < n)N *= 2;
    set<int>st;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        upd(i, x);
        st.insert(i);
    }
    st.insert(1e18);
    while (q--) {
        int o; cin >> o;
        if (o == 1) {
            int idx, x;
            cin >> idx >> x;
            st.insert(idx);
            upd(idx, x);
        }
        if (o == 2) {
            int ll, rr;
            cin >> ll >> rr;
            auto s = st.lower_bound(ll);
            auto e = st.upper_bound(rr);
            vector<int>v;
            while (s != e) {
                int idx = *s;
                upd(idx, seg[idx - 1 + N] / k);
                if (seg[idx - 1 + N] == 0)v.push_back(*s);
                s++;
            }
            for (auto i : v)st.erase(i);
        }
        if (o == 3) {
            cin >> l >> r;
            cout << calc(1, N, 1) << endl;
        }
    }
}

Compilation message

sterilizing.cpp:8:46: warning: overflow in conversion from 'double' to 'int' changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
    8 | const int sz = 1e6 + 1, mod = 1e9 + 7, inf = -1e18;
      |                                              ^~~~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:41:15: warning: overflow in conversion from 'double' to 'std::set<int>::value_type' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   41 |     st.insert(1e18);
      |               ^~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 596 KB Output is correct
2 Correct 41 ms 2816 KB Output is correct
3 Correct 55 ms 2900 KB Output is correct
4 Correct 137 ms 1768 KB Output is correct
5 Correct 181 ms 6016 KB Output is correct
6 Correct 180 ms 6184 KB Output is correct
7 Execution timed out 5050 ms 6052 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

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