Soluție HackerRank pentru Array and Queries. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Array and Queries

Cerinta completa

Given an array, you are asked to perform a number of queries and divide the array into what are called, beautiful subsequences.

The array [Expresie matematică indisponibilă în copia arhivată] has length [Expresie matematică indisponibilă în copia arhivată]. A function [Expresie matematică indisponibilă în copia arhivată] is defined to be a minimal possible [Expresie matematică indisponibilă în copia arhivată], such that it’s possible to divide array [Expresie matematică indisponibilă în copia arhivată] into [Expresie matematică indisponibilă în copia arhivată] beautiful subsequences. Note that each element of an array should belong to exactly one subsequence, and subsequence does not necessarily need to be consecutive.

A subsequence [Expresie matematică indisponibilă în copia arhivată] with length [Expresie matematică indisponibilă în copia arhivată] is called beautiful if and only if:

  • [Expresie matematică indisponibilă în copia arhivată] or
  • Let [Expresie matematică indisponibilă în copia arhivată] be a sorted version of [Expresie matematică indisponibilă în copia arhivată]. It must hold that [Expresie matematică indisponibilă în copia arhivată] for every [Expresie matematică indisponibilă în copia arhivată]

For instance, if [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată] would be [Expresie matematică indisponibilă în copia arhivată]. Because, you can divide [Expresie matematică indisponibilă în copia arhivată] into [Expresie matematică indisponibilă în copia arhivată] beautiful subsequences either like [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată] or like [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată].

You have to answer [Expresie matematică indisponibilă în copia arhivată] queries. Each query is of the type:

  • [Expresie matematică indisponibilă în copia arhivată] [Expresie matematică indisponibilă în copia arhivată]: you need to change a value of [Expresie matematică indisponibilă în copia arhivată] to [Expresie matematică indisponibilă în copia arhivată], i.e. [Expresie matematică indisponibilă în copia arhivată]. Here [Expresie matematică indisponibilă în copia arhivată] is [Expresie matematică indisponibilă în copia arhivată].

After each query, for the value of [Expresie matematică indisponibilă în copia arhivată], lets denote that value as [Expresie matematică indisponibilă în copia arhivată], where [Expresie matematică indisponibilă în copia arhivată] indicates the [Expresie matematică indisponibilă în copia arhivată] query.

You need to find [Expresie matematică indisponibilă în copia arhivată] modulo [Expresie matematică indisponibilă în copia arhivată].

Input Format

The first line contains a single integer [Expresie matematică indisponibilă în copia arhivată], representing the length of array [Expresie matematică indisponibilă în copia arhivată].
The next line contains the array [Expresie matematică indisponibilă în copia arhivată] given as space-separated integers.
The next line contains a single integer [Expresie matematică indisponibilă în copia arhivată], representing the number of queries.
Each of the [Expresie matematică indisponibilă în copia arhivată] lines contain two integers [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată], which is described above.

Constraints

  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]

Output Format

Print the required answer in one line.

Sample Input 0

5
2 2 1 1 1
2
3 2
5 5

Sample Output 0

11

Explanation 0

The initial array [Expresie matematică indisponibilă în copia arhivată] is [Expresie matematică indisponibilă în copia arhivată]

  • After [Expresie matematică indisponibilă în copia arhivată] query the array becomes [Expresie matematică indisponibilă în copia arhivată] this can be divided into [Expresie matematică indisponibilă în copia arhivată] subsequences as [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată].
  • After [Expresie matematică indisponibilă în copia arhivată] query the array becomes [Expresie matematică indisponibilă în copia arhivată] this can be divided into [Expresie matematică indisponibilă în copia arhivată] subsequences as [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată].

image

Hence, calculating [Expresie matematică indisponibilă în copia arhivată] we get

[Expresie matematică indisponibilă în copia arhivată]

Sample Input 1

2
3 3
3
2 4
1 5
2 2

Sample Output 1

9

Explanation 1

The initial array [Expresie matematică indisponibilă în copia arhivată] is [Expresie matematică indisponibilă în copia arhivată]

  • After [Expresie matematică indisponibilă în copia arhivată] query the array becomes [Expresie matematică indisponibilă în copia arhivată] this can be divided into [Expresie matematică indisponibilă în copia arhivată] subsequence as [Expresie matematică indisponibilă în copia arhivată].
  • After [Expresie matematică indisponibilă în copia arhivată] query the array becomes [Expresie matematică indisponibilă în copia arhivată] this can be divided into [Expresie matematică indisponibilă în copia arhivată] subsequence as [Expresie matematică indisponibilă în copia arhivată].
  • After [Expresie matematică indisponibilă în copia arhivată] query the array becomes [Expresie matematică indisponibilă în copia arhivată] this can be divided into [Expresie matematică indisponibilă în copia arhivată] subsequences as [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată].

Hence, calculating [Expresie matematică indisponibilă în copia arhivată] we get

[Expresie matematică indisponibilă în copia arhivată]

Limbajul de programare folosit: cpp14

Cod:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int INF = (int) 1e9 + 123;
const ll LINF = (ll) 1e18 + 123;
const ld EPS = (ld) 1e-8;
const ll MOD = (ll) 1e9 + 7;

#define sz(x) (int) (x).size()
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb(s, t, x) (int) (lower_bound(s, t, x) - s)
#define ub(s, t, x) (int) (upper_bound(s, t, x) - s)
#define rep(i, f, t) for (auto i = f; i < t; i++)
#define per(i, f, t) for (auto i = f; i >= t; i--)

inline void add(ll &x, ll y, ll mod = MOD) {
    x += y;
    if (x >= mod) x -= mod;
    if (x < 0) x += mod;
}

void run();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    run();
    return 0;
}

// == SOLUTION == //

const int N = (int) 3e5 + 123;

int n, q;
int a[N];
unordered_map<int, int> cnt;

int get(int x) {
    auto it = cnt.find(x);
    return (it == cnt.end() ? 0 : it->second);
}

int potential(int val) {
    int v = get(val);
    return (v == 0 ? 0 : max(0, v - get(val - 1)));
}

int potential(vector<int> pos) {
    sort(all(pos));
    pos.resize(unique(all(pos)) - pos.begin());
    int res = 0;
    for (int p : pos) {
        res += potential(p);
    }
    return res;
}

void run() {
    cin >> n;
    rep(i, 1, n + 1) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    cin >> q;
    ll cur = 0;
    for (auto &it : cnt) {
        cur += potential(it.first);
    }

    ll ans = 0;
    rep(i, 1, q + 1) {
        int id, val;
        cin >> id >> val;
        int was = a[id];
        cur -= potential({was, was + 1, val, val + 1});
        cnt[was]--;
        a[id] = val;
        cnt[val]++;
        cur += potential({was, was + 1, val, val + 1});
        add(ans, i * cur % MOD);
    }

    cout << ans << "\n";
}

Scor obtinut: 1.0

Submission ID: 464668424

Link challenge: https://www.hackerrank.com/challenges/array-and-queries-1/problem

Array and Queries