oj.uz

Submission #957752

# Submission time Handle Problem Language Result Execution time Memory
957752 2024-04-04T09:18:38 Z Neco_arc Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 5144 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 + 1, l, mid
#define _right id + 2 * (mid - l + 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 {
        int Amax, Amin;
        ll Sum;
    } st[2 * maxn];
    int store[2 * maxn];

    #define L id + 1
    #define R id + 2 * (mid - l + 1)

    void down(int id, int l, int r)
    {
        int val = store[id], mid = (l + r) >> 1;
        if(val < 0) return;

        st[L].Amax = st[L].Amin = val;
        st[L].Sum = 1ll * val * (mid - l + 1);

        st[R].Amax = st[R].Amin = val;
        st[R].Sum = 1ll * val * (r - mid);

        store[L] = store[R] = val;

        store[id] = -1;
    }

    Node cb(Node x, Node y) {
        return {max(x.Amax, y.Amax), min(x.Amin, y.Amin), x.Sum + y.Sum};
    }

    void updateVal(int u, int v, int val, int id = 0, int l = 1, int r = n)
    {
        if(l > u || r < v) return;
        if(u <= l && r <= v) return void(st[id].Amax = st[id].Amin = st[id].Sum = val);
        down(id, l, r);
        int mid = (l + r) >> 1;
        updateVal(u, v, val, _left), updateVal(u, v, val, _right);

        st[id] = cb(st[L], st[R]);
    }

    void update(int u, int v, int id = 0, int l = 1, int r = n)
    {
        if(l > v || r < u) return;
        if(u <= l && r <= v && st[id].Amin == st[id].Amax)
        {
            st[id].Amin = st[id].Amax = st[id].Amax / k;
            st[id].Sum = 1ll * st[id].Amax * (r - l + 1);
            store[id] = st[id].Amax;

            return;
        }

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

        st[id] = cb(st[L], st[R]);
    }


    ll get(int u, int v, int id = 0, 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;
        down(id, l, r);
        return get(u, v, _left) + get(u, v, _right);
    }

    #undef L
    #undef R

} St;

void solve()
{

    cin >> n >> q >> k;

    int X;
    fi(i, 0, 2 * n) St.store[i] = -1;
    fi(i, 1, n) cin >> X, St.updateVal(i, i, X);

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

        if(type == 1) St.updateVal(x, x, y);
        if(type == 2) St.update(x, y);
        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:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         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 3 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 600 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 4 ms 584 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 4 ms 592 KB Output is correct
12 Correct 5 ms 504 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4862 ms 2788 KB Output is correct
2 Correct 2974 ms 2292 KB Output is correct
3 Correct 4742 ms 3720 KB Output is correct
4 Execution timed out 5052 ms 5144 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 600 KB Output is correct
2 Correct 19 ms 2140 KB Output is correct
3 Correct 25 ms 2228 KB Output is correct
4 Correct 54 ms 1372 KB Output is correct
5 Correct 81 ms 4188 KB Output is correct
6 Correct 81 ms 4188 KB Output is correct
7 Execution timed out 5002 ms 4944 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 2648 KB Output is correct
2 Correct 97 ms 2640 KB Output is correct
3 Correct 103 ms 2140 KB Output is correct
4 Correct 116 ms 1968 KB Output is correct
5 Correct 143 ms 4604 KB Output is correct
6 Correct 156 ms 4436 KB Output is correct
7 Correct 135 ms 4620 KB Output is correct
8 Correct 190 ms 4648 KB Output is correct
9 Correct 166 ms 4620 KB Output is correct
10 Correct 188 ms 4648 KB Output is correct
11 Correct 146 ms 4740 KB Output is correct
12 Correct 246 ms 4692 KB Output is correct