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.

1#include <bits/stdc++.h>
2using namespace std;
3 
4using ll = long long;
5using ld = long double;
6using db = double; 
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;

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

1#include <bits/stdc++.h>
2using namespace std;
3 
4using ll = long long;
5using ld = long double;
6using db = double; 
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;

Solution 2

Just use indexed set!

1#include <bits/stdc++.h>
2#include <ext/pb_ds/tree_policy.hpp>
3#include <ext/pb_ds/assoc_container.hpp>
4 
5using namespace std;
6using namespace __gnu_pbds;
7 
8typedef long long ll;
9typedef vector<int> vi;
10typedef pair<int, int> pii;