oj.uz

Submission #957659

# Submission time Handle Problem Language Result Execution time Memory
957659 2024-04-04T07:14:35 Z vjudge1 Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 13160 KB 
#include <bits/stdc++.h>
#define Y8o "Sterilizing Spray"
#define maxn 100005
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)

using namespace std;

/// okay?
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);
}
void iof()   /// ------------------inp_out file!-----------------///
{
    if(fopen(Y8o".inp", "r"))
    {
        freopen(Y8o".inp", "r", stdin);
        freopen(Y8o".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
void ctime()   /// ------------------check time!-----------------///
{
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}
/// okay!

int n, Q, k;
int a[maxn];
struct dl
{
    int id, f, s;
} qr[maxn];
pii st[4 * maxn]; /// max + pos
ll st2[4 * maxn]; /// sum

void build(int id = 1, int l = 1, int r = n)
{
    if(l == r)
    {
        st[id] = {a[l], l};
        st2[id] = 1ll * a[l];
        return ;
    }

    int mid = (l + r) >> 1;

    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);

    st[id] = max(st[id * 2], st[id * 2 + 1]);
    st2[id] = st2[id * 2] + st2[id * 2 + 1];
}

void update(int i, int val, int id = 1, int l = 1, int r = n)
{
    if(i < l || r < i) return ;
    if(l == r)
    {
        st[id] = {val, l};
        st2[id] = 1ll * val;
        return ;
    }

    int mid = (l + r) >> 1;

    update(i, val, id * 2, l, mid);
    update(i, val, id * 2 + 1, mid + 1, r);

    st[id] = max(st[id * 2], st[id * 2 + 1]);
    st2[id] = st2[id * 2] + st2[id * 2 + 1];
}

pii getma(int u, int v, int id = 1, int l = 1, int r = n)
{
    if(v < l || r < u) return {0, 0};
    if(u <= l && r <= v) return st[id];

    int mid = (l + r) >> 1;

    return max( getma(u, v, id * 2, l, mid), getma(u, v, id * 2 + 1, mid + 1, r) );
}

ll getsum(int u, int v, int id = 1, int l = 1, int r = n)
{
    if(v < l || r < u) return 0;
    if(u <= l && r <= v) return st2[id];

    int mid = (l + r) >> 1;

    return getsum(u, v, id * 2, l, mid) + getsum(u, v, id * 2 + 1, mid + 1, r);
}

void solve()
{
    cin >> n >> Q >> k;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= Q; i ++) cin >> qr[i].id >> qr[i].f >> qr[i].s;

    build();

    for(int i = 1; i <= Q; i ++)
    {
        int id = qr[i].id, u = qr[i].f, v = qr[i].s, l = u, r = v;
        if(id == 1) update(u, v); /// a[u] = v
        else if(id == 2)
        {
            vector<pii> store;

            while(1)
            {
                pii best = getma(l, r);
                if(best.first != 0)
                {
                    store.push_back(best);
                    update(best.second, 0);
                }
                else break;
            }
            for(pii x : store)
            {
                int val = x.first, pos = x.second;
                update(pos, val / k);
            }
            store.clear();
        }
        else cout << getsum(l, r) << '\n';
    }
}


int main()
{
    iof();

    int nTest = 1;
//    cin >> nTest;

    while(nTest --)
    {
        solve();
    }

    ctime();
    return 0;
}

Compilation message

sterilizing.cpp: In function 'void iof()':
sterilizing.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen(Y8o".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(Y8o".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4696 KB Output is correct
2 Correct 27 ms 4640 KB Output is correct
3 Correct 8 ms 4444 KB Output is correct
4 Correct 26 ms 4952 KB Output is correct
5 Correct 26 ms 4700 KB Output is correct
6 Correct 17 ms 4700 KB Output is correct
7 Correct 23 ms 4696 KB Output is correct
8 Correct 23 ms 4700 KB Output is correct
9 Correct 31 ms 4776 KB Output is correct
10 Correct 21 ms 4776 KB Output is correct
11 Correct 21 ms 4696 KB Output is correct
12 Correct 23 ms 4776 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5030 ms 11152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5464 KB Output is correct
2 Correct 21 ms 7472 KB Output is correct
3 Correct 26 ms 7512 KB Output is correct
4 Correct 55 ms 9296 KB Output is correct
5 Correct 86 ms 9856 KB Output is correct
6 Correct 83 ms 9904 KB Output is correct
7 Execution timed out 5077 ms 10576 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 9816 KB Output is correct
2 Correct 438 ms 10124 KB Output is correct
3 Correct 1029 ms 9492 KB Output is correct
4 Correct 550 ms 10412 KB Output is correct
5 Correct 837 ms 11652 KB Output is correct
6 Correct 1067 ms 11560 KB Output is correct
7 Correct 773 ms 12180 KB Output is correct
8 Correct 1523 ms 12576 KB Output is correct
9 Correct 1340 ms 12368 KB Output is correct
10 Correct 1638 ms 12380 KB Output is correct
11 Correct 965 ms 12380 KB Output is correct
12 Correct 2513 ms 13160 KB Output is correct