Atcoder Weekday Contest 015

auto solve = [](){
    vi a(7),b(7);
    ri(a); ri(b);
    for(int i = 0; i < si(a); i++) res += (a[i] * b[i]);
    po(res);
};

int n,k;
 
auto solve = [](){
    ri(n, k);
    for(int i = 1; i <= n; i++){
        int x; ri(x);
        if(x >= k){
            po(i);
            return;
        }
    }
    po(-1);
};

int n,res;
safe_map<int, safe_map<int, int>> M;
safe_map<int, int> C;
 
auto solve = [](){
    ri(n);
    for(int i = 0; i < n; i++){
        int a,b; ri(a, b);
        M[a][b]++;
        C[a]++;
    }
    for(const auto& [a, b] : M){
        int cnt = C[a];
        res += (cnt * (cnt - 1)) / 2;
        for(const auto& [x, y] : b){
            int cnt2 = y;
            res -= (cnt2 * (cnt2 - 1)) / 2;
        }
    }
    po(res);
};

int n,m,k,res;
 
auto solve = [](){
    ri(n, m, k);
    multiset<int> s;
    for(int i = 0; i < n; i++){
        int x; ri(x); s.insert(x);
    }
    for(int i = 0; i < m; i++){
        int x; ri(x);
        auto it = s.lower_bound(x);
        if(it == s.end()) continue;
        s.erase(it);
        res++;
    }
    po(res * k);
};

const int sz = 1 << 17;
int n, sqrtN, q;
struct query{
    int l, r, idx;
    bool operator<(const query& other) const {
        int block_this = l / sqrtN;
        int block_other = other.l / sqrtN;
        if (block_this != block_other) {
            return block_this < block_other;
        }
        return (block_this & 1) ? (r < other.r) : (r > other.r);
    }
};
int v[sz];
int res[sz]; 
int cnt[sz]; 
int cur;
 
void Push(int x){
    if(cnt[v[x]] == 0) cur++;
    cnt[v[x]]++;
}
 
void Pop(int x){
    cnt[v[x]]--;
    if(cnt[v[x]] == 0) cur--;
}
 
auto solve = [](){
    ri(n, q);
    for(int i = 1; i <= n; i++) ri(v[i]);
    sqrtN = sqrt(n);
    vector<query> Q(q);
    for(int i = 0; i < q; i++){
        int l,r; ri(l, r);
        Q[i] = {l, r, i + 1};
    }
    sort(all(Q));
    int L = 1, R = 0;
    for(const auto& [l, r, idx] : Q){
        while(L > l) { L--; Push(L); }
        while(R < r) { R++; Push(R); }
        while(L < l) { Pop(L); L++; }
        while(R > r) { Pop(R); R--; }
        res[idx] = cur;
    }
    for(int i = 1; i <= q; i++) po(res[i]);
};