oj.uz

Submission #571250

# Submission time Handle Problem Language Result Execution time Memory
571250 2022-06-01T15:25:25 Z Tien_Noob Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 983 ms 9232 KB 
//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 1e5;
int n, q, a[N + 1], k;
set<int> num;
struct FenwickTree
{
    long long tree[N + 1];
    void add(int pos, int val)
    {
        for (; pos <= n; pos += (pos & (-pos)))
        {
            tree[pos] += val;
        }
    }
    long long sum(int pos)
    {
        long long ret = 0;
        for (; pos > 0; pos -= (pos & (-pos)))
        {
            ret += tree[pos];
        }
        return ret;
    }
    long long sum(int l, int r)
    {
        return sum(r) - sum(l - 1);
    }
} tree;
void read()
{
    cin >> n >> q >> k;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> a[i];
        if (a[i])
        {
            num.insert(i);
            tree.add(i, a[i]);
        }
    }
}
void solve()
{
    while(q--)
    {
        int t;
        cin >> t;
        if (t == 1)
        {
            int i, x;
            cin >> i >> x;
            tree.add(i, -a[i]);
            a[i] = x;
            tree.add(i, a[i]);
            if (a[i])
            {
                num.insert(i);
            }
        }
        else if (t == 2)
        {
            int l, r;
            cin >> l >> r;
            if (k == 1)
            {
                continue;
            }
            vector<int> valid;
            while(true)
            {
                auto it = num.lower_bound(l);
                if (it == num.end() || *it > r)
                {
                    for (int i : valid)
                    {
                        num.insert(i);
                    }
                    break;
                }
                tree.add(*it, -a[*it]);
                a[*it] /= k;
                if (a[*it])
                {
                    tree.add(*it, a[*it]);
                    valid.push_back(*it);
                }
                num.erase(it);
            }
        }
        else
        {
            int l, r;
            cin >> l >> r;
            cout << tree.sum(l, r) << '\n';
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case #" << __ << ":" << '\n';
        read();
        solve();
    }
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 12 ms 488 KB Output is correct
5 Correct 14 ms 596 KB Output is correct
6 Correct 9 ms 592 KB Output is correct
7 Correct 16 ms 584 KB Output is correct
8 Correct 13 ms 592 KB Output is correct
9 Correct 17 ms 608 KB Output is correct
10 Correct 11 ms 596 KB Output is correct
11 Correct 12 ms 596 KB Output is correct
12 Correct 13 ms 600 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 5560 KB Output is correct
2 Correct 47 ms 4276 KB Output is correct
3 Correct 62 ms 6812 KB Output is correct
4 Correct 86 ms 8564 KB Output is correct
5 Correct 97 ms 9064 KB Output is correct
6 Correct 102 ms 9024 KB Output is correct
7 Correct 80 ms 9072 KB Output is correct
8 Correct 96 ms 9004 KB Output is correct
9 Correct 84 ms 8952 KB Output is correct
10 Correct 83 ms 9088 KB Output is correct
11 Correct 107 ms 8864 KB Output is correct
12 Correct 111 ms 8924 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 980 KB Output is correct
2 Correct 15 ms 2132 KB Output is correct
3 Correct 20 ms 2280 KB Output is correct
4 Correct 32 ms 2356 KB Output is correct
5 Correct 68 ms 5208 KB Output is correct
6 Correct 53 ms 5264 KB Output is correct
7 Correct 68 ms 5716 KB Output is correct
8 Correct 65 ms 5280 KB Output is correct
9 Correct 48 ms 5152 KB Output is correct
10 Correct 66 ms 5096 KB Output is correct
11 Correct 51 ms 5068 KB Output is correct
12 Correct 61 ms 5148 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 5256 KB Output is correct
2 Correct 177 ms 5408 KB Output is correct
3 Correct 377 ms 4596 KB Output is correct
4 Correct 217 ms 4232 KB Output is correct
5 Correct 336 ms 9056 KB Output is correct
6 Correct 411 ms 9192 KB Output is correct
7 Correct 312 ms 9008 KB Output is correct
8 Correct 738 ms 8976 KB Output is correct
9 Correct 553 ms 8856 KB Output is correct
10 Correct 698 ms 9100 KB Output is correct
11 Correct 376 ms 9232 KB Output is correct
12 Correct 983 ms 9068 KB Output is correct