Codeforces Round 849 (Div. 4)

Link: https://codeforces.com/contest/1791

F. Range Update Point Query

Prompt

• 2 types of queries
  • 1 l r: update a[i] for l <= i <= r to the sum of its digits
  • 2 x: print a[x]

Constraints

• 1 <= a[i] <= 10^9
• 1 <= n <= 2 * 10^5
• 1 <= q <= 2 * 10^5

Reason

• any a[i] only updates for at most 2 times
  • 99999999 -> 8 * 9 = 72 -> 7 + 2 = 9
• keep track of the a[i] that can still be updated and only update them
• set (sorted) + binary search
• time complexity: \(O(q+nlogn)\)
  • \(O(logn)\) for updating each element
  • at most \(3\) operations for each element
  • at most \(3nlogn\) updates
• space complexity: \(O(n)\)

Solution

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>
using namespace std;

#define PII pair<int, int>
#define LL long long

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    set<int> cache;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] >= 10)
            cache.insert(i);
    }

    for (int i = 0; i < q; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r;
            cin >> l >> r;
            l--, r--;
            for (auto j = cache.lower_bound(l);
                 !cache.empty() && j != cache.end() && *j <= r;) {
                int s = 0;
                while (a[*j]) {
                    s += a[*j] % 10;
                    a[*j] /= 10;
                }
                a[*j] = s;
                if (s < 10)
                    j = cache.erase(j);
                else
                    j++;
            }
        } else {
            int x;
            cin >> x;
            x--;
            cout << a[x] << endl;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

G2. Teleporters (Hard Version)

Prompt

Constraints

Reason

Solution