oj.uz

Submission #957734

# Submission time Handle Problem Language Result Execution time Memory
957734 2024-04-04T08:59:48 Z Neco_arc Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 5212 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"
#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:92:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 532 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 2 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 600 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 3 ms 604 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3606 ms 2980 KB Output is correct
2 Correct 2375 ms 2912 KB Output is correct
3 Correct 3756 ms 4996 KB Output is correct
4 Execution timed out 5047 ms 5212 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 664 KB Output is correct
2 Correct 13 ms 2532 KB Output is correct
3 Correct 19 ms 2336 KB Output is correct
4 Correct 37 ms 1372 KB Output is correct
5 Correct 58 ms 4576 KB Output is correct
6 Correct 60 ms 4444 KB Output is correct
7 Execution timed out 5033 ms 4992 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 2640 KB Output is correct
2 Correct 68 ms 2640 KB Output is correct
3 Correct 67 ms 2632 KB Output is correct
4 Correct 82 ms 1632 KB Output is correct
5 Correct 100 ms 4608 KB Output is correct
6 Correct 107 ms 4824 KB Output is correct
7 Correct 89 ms 4692 KB Output is correct
8 Correct 110 ms 4824 KB Output is correct
9 Correct 109 ms 4676 KB Output is correct
10 Correct 123 ms 4692 KB Output is correct
11 Correct 90 ms 4688 KB Output is correct
12 Correct 153 ms 4692 KB Output is correct