oj.uz

Submission #957755

# Submission time Handle Problem Language Result Execution time Memory
957755 2024-04-04T09:19:58 Z Neco_arc Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 206 ms 6348 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 + 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 && k > 1) 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:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:138:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2644 KB Output is correct
2 Correct 39 ms 2128 KB Output is correct
3 Correct 39 ms 3676 KB Output is correct
4 Correct 54 ms 4436 KB Output is correct
5 Correct 59 ms 6348 KB Output is correct
6 Correct 67 ms 6232 KB Output is correct
7 Correct 64 ms 6280 KB Output is correct
8 Correct 59 ms 6316 KB Output is correct
9 Correct 57 ms 6216 KB Output is correct
10 Correct 57 ms 5912 KB Output is correct
11 Correct 62 ms 6108 KB Output is correct
12 Correct 55 ms 5972 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 604 KB Output is correct
2 Correct 17 ms 2140 KB Output is correct
3 Correct 22 ms 2140 KB Output is correct
4 Correct 53 ms 1464 KB Output is correct
5 Correct 75 ms 4184 KB Output is correct
6 Correct 76 ms 4444 KB Output is correct
7 Correct 59 ms 4432 KB Output is correct
8 Correct 83 ms 5412 KB Output is correct
9 Correct 69 ms 5116 KB Output is correct
10 Correct 70 ms 4956 KB Output is correct
11 Correct 69 ms 4948 KB Output is correct
12 Correct 70 ms 4996 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 2632 KB Output is correct
2 Correct 87 ms 2548 KB Output is correct
3 Correct 92 ms 2240 KB Output is correct
4 Correct 103 ms 1872 KB Output is correct
5 Correct 125 ms 4380 KB Output is correct
6 Correct 139 ms 4480 KB Output is correct
7 Correct 130 ms 4940 KB Output is correct
8 Correct 164 ms 4436 KB Output is correct
9 Correct 142 ms 4528 KB Output is correct
10 Correct 163 ms 4620 KB Output is correct
11 Correct 127 ms 4432 KB Output is correct
12 Correct 206 ms 4688 KB Output is correct