oj.uz

Submission #571226

# Submission time Handle Problem Language Result Execution time Memory
571226 2022-06-01T15:12:05 Z YouAreMyGalaxy Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 1037 ms 9240 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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 6 ms 468 KB Output is correct
4 Correct 17 ms 476 KB Output is correct
5 Correct 16 ms 596 KB Output is correct
6 Correct 10 ms 596 KB Output is correct
7 Correct 13 ms 608 KB Output is correct
8 Correct 13 ms 596 KB Output is correct
9 Correct 19 ms 588 KB Output is correct
10 Correct 15 ms 596 KB Output is correct
11 Correct 14 ms 640 KB Output is correct
12 Correct 16 ms 600 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 5508 KB Output is correct
2 Correct 69 ms 4296 KB Output is correct
3 Correct 77 ms 6736 KB Output is correct
4 Correct 94 ms 8528 KB Output is correct
5 Correct 111 ms 9036 KB Output is correct
6 Correct 106 ms 9020 KB Output is correct
7 Correct 121 ms 8996 KB Output is correct
8 Correct 103 ms 9088 KB Output is correct
9 Correct 110 ms 8940 KB Output is correct
10 Correct 119 ms 8976 KB Output is correct
11 Correct 106 ms 8960 KB Output is correct
12 Correct 86 ms 9016 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 928 KB Output is correct
2 Correct 15 ms 2132 KB Output is correct
3 Correct 18 ms 2240 KB Output is correct
4 Correct 34 ms 2348 KB Output is correct
5 Correct 53 ms 5232 KB Output is correct
6 Correct 54 ms 5224 KB Output is correct
7 Correct 55 ms 5672 KB Output is correct
8 Correct 54 ms 5216 KB Output is correct
9 Correct 51 ms 5156 KB Output is correct
10 Correct 49 ms 5060 KB Output is correct
11 Correct 49 ms 5068 KB Output is correct
12 Correct 55 ms 5148 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 5184 KB Output is correct
2 Correct 197 ms 5408 KB Output is correct
3 Correct 473 ms 4480 KB Output is correct
4 Correct 298 ms 4304 KB Output is correct
5 Correct 468 ms 9096 KB Output is correct
6 Correct 454 ms 9160 KB Output is correct
7 Correct 340 ms 9080 KB Output is correct
8 Correct 646 ms 9072 KB Output is correct
9 Correct 503 ms 8948 KB Output is correct
10 Correct 684 ms 9028 KB Output is correct
11 Correct 445 ms 9240 KB Output is correct
12 Correct 1037 ms 9024 KB Output is correct