oj.uz

Submission #957750

# Submission time Handle Problem Language Result Execution time Memory
957750 2024-04-04T09:15:11 Z Neco_arc Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 10396 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, Amin, Sum;
    } st[4 * maxn];
    int store[4 * maxn];

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

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

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

        store[id * 2] = store[id * 2 + 1] = 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 = 1, 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[id * 2], st[id * 2 + 1]);
    }

    void update(int u, int v, int id = 1, 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 = 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[id * 2], st[id * 2 + 1]);
    }


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

} St;

void solve()
{

    cin >> n >> q >> k;

    int X;
    fi(i, 1, 4 * 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:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:131:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 2 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 4 ms 4700 KB Output is correct
6 Correct 4 ms 4700 KB Output is correct
7 Correct 4 ms 4956 KB Output is correct
8 Correct 4 ms 4700 KB Output is correct
9 Correct 4 ms 4700 KB Output is correct
10 Correct 4 ms 4700 KB Output is correct
11 Correct 4 ms 4784 KB Output is correct
12 Correct 4 ms 4804 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4655 ms 6416 KB Output is correct
2 Correct 2901 ms 7536 KB Output is correct
3 Correct 4845 ms 9828 KB Output is correct
4 Execution timed out 5039 ms 9796 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4700 KB Output is correct
2 Correct 17 ms 6764 KB Output is correct
3 Correct 22 ms 6748 KB Output is correct
4 Correct 53 ms 4752 KB Output is correct
5 Correct 74 ms 9236 KB Output is correct
6 Correct 76 ms 9304 KB Output is correct
7 Execution timed out 5086 ms 9808 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 5716 KB Output is correct
2 Correct 96 ms 5752 KB Output is correct
3 Correct 96 ms 6788 KB Output is correct
4 Correct 112 ms 4900 KB Output is correct
5 Correct 141 ms 9556 KB Output is correct
6 Correct 150 ms 9556 KB Output is correct
7 Correct 127 ms 9552 KB Output is correct
8 Correct 173 ms 9552 KB Output is correct
9 Correct 149 ms 10112 KB Output is correct
10 Correct 169 ms 9552 KB Output is correct
11 Correct 134 ms 9648 KB Output is correct
12 Correct 229 ms 10396 KB Output is correct