oj.uz

Submission #957739

# Submission time Handle Problem Language Result Execution time Memory
957739 2024-04-04T09:01:45 Z Neco_arc Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 6360 KB 
#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define Neco "Sterilizing Spray"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 1e5 + 7

using namespace std;

const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll GetRandom(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r)(rng);
}

int n, q, k;

struct IT {
    struct Node {
        ll Amax, Sum;
    } st[4 * maxn];

    void update(int u, int v, int val, int id = 1, int l = 1, int r = n)
    {
        if(l > v || r < u) return;
        if(st[id].Amax <= 0 && val < 0) return;

        if(l == r) {
            st[id].Sum = val < 0 ? st[id].Sum / k : val;
            st[id].Amax = st[id].Sum;
            return;
        }

        int mid = (l + r) >> 1;
        update(u, v, val, _left), update(u, v, val, _right);

        st[id].Amax = max(st[id * 2].Amax, st[id * 2 + 1].Amax);
        st[id].Sum = st[id * 2].Sum + st[id * 2 + 1].Sum;
    }

    ll get(int u, int v, int id = 1, int l = 1, int r = n)
    {
        if(l > v || r < u) return 0;
        if(u <= l && r <= v) return st[id].Sum;

        int mid = (l + r) >> 1;
        return get(u, v, _left) + get(u, v, _right);
    }

} St;

void solve()
{

    cin >> n >> q >> k;

    int X;
    fi(i, 1, n) cin >> X, St.update(i, i, X);

    fi(i, 1, q) {
        int type, x, y;
        cin >> type >> x >> y;

        if(type == 1) St.update(x, x, y);
        if(type == 2) St.update(x, y, -1);
        if(type == 3) cout << St.get(x, y) << '\n';
    }

}


int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(Neco".inp", "r")) {
        freopen(Neco".inp", "r", stdin);
        freopen(Neco".out", "w", stdout);
    }


    int nTest = 1;
//    cin >> nTest;


    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 3 ms 588 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3719 ms 2868 KB Output is correct
2 Correct 2368 ms 2796 KB Output is correct
3 Correct 3786 ms 5152 KB Output is correct
4 Execution timed out 5039 ms 6004 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1116 KB Output is correct
2 Correct 13 ms 2648 KB Output is correct
3 Correct 17 ms 2908 KB Output is correct
4 Correct 38 ms 2324 KB Output is correct
5 Correct 68 ms 5464 KB Output is correct
6 Correct 65 ms 5540 KB Output is correct
7 Execution timed out 5089 ms 5720 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 3472 KB Output is correct
2 Correct 69 ms 3740 KB Output is correct
3 Correct 67 ms 3216 KB Output is correct
4 Correct 76 ms 2644 KB Output is correct
5 Correct 94 ms 6220 KB Output is correct
6 Correct 107 ms 6264 KB Output is correct
7 Correct 90 ms 6360 KB Output is correct
8 Correct 125 ms 6148 KB Output is correct
9 Correct 110 ms 6056 KB Output is correct
10 Correct 111 ms 6000 KB Output is correct
11 Correct 109 ms 5984 KB Output is correct
12 Correct 143 ms 5952 KB Output is correct