CSES - Salary Queries

Solution 1

As mentioned in the module, you can apply coordinate compression before using a segment tree or a BIT.

Stick with arrays (or vectors) whenever possible; using a map instead may TLE.

Copy
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MX = 4e5 + 5;

ll bit[MX];
vector<int> vals;
int n, q;

Here is a similar solution with a map that passes slightly under the time limit.

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using db = double;
using str = string;  // yay python!

using pi = pair<int, int>;
using pl = pair<ll, ll>;

Solution 2

Just use indexed set!

Copy
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
template <class T>