oj.uz

Submission #957756

# Submission time Handle Problem Language Result Execution time Memory
957756 2024-04-04T09:20:26 Z vjudge1 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 219 ms 5024 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 1 ms 348 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 348 KB Output is correct
6 Correct 3 ms 520 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 5 ms 592 KB Output is correct
9 Correct 4 ms 600 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 3 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2652 KB Output is correct
2 Correct 40 ms 2052 KB Output is correct
3 Correct 40 ms 3692 KB Output is correct
4 Correct 57 ms 4904 KB Output is correct
5 Correct 59 ms 4688 KB Output is correct
6 Correct 60 ms 4692 KB Output is correct
7 Correct 58 ms 4816 KB Output is correct
8 Correct 57 ms 4692 KB Output is correct
9 Correct 57 ms 4688 KB Output is correct
10 Correct 56 ms 5024 KB Output is correct
11 Correct 55 ms 4832 KB Output is correct
12 Correct 54 ms 4692 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 600 KB Output is correct
2 Correct 16 ms 2136 KB Output is correct
3 Correct 22 ms 2140 KB Output is correct
4 Correct 56 ms 1372 KB Output is correct
5 Correct 77 ms 4408 KB Output is correct
6 Correct 77 ms 4400 KB Output is correct
7 Correct 55 ms 4272 KB Output is correct
8 Correct 76 ms 4376 KB Output is correct
9 Correct 88 ms 4184 KB Output is correct
10 Correct 72 ms 4188 KB Output is correct
11 Correct 69 ms 4380 KB Output is correct
12 Correct 75 ms 4188 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 2636 KB Output is correct
2 Correct 87 ms 2596 KB Output is correct
3 Correct 88 ms 2284 KB Output is correct
4 Correct 105 ms 1872 KB Output is correct
5 Correct 128 ms 4432 KB Output is correct
6 Correct 143 ms 4432 KB Output is correct
7 Correct 122 ms 4620 KB Output is correct
8 Correct 161 ms 4580 KB Output is correct
9 Correct 147 ms 4520 KB Output is correct
10 Correct 161 ms 4556 KB Output is correct
11 Correct 125 ms 4432 KB Output is correct
12 Correct 219 ms 4892 KB Output is correct