Cod sursa(job #3247448)

Utilizator S80P_ShadeslayerBadarau Andrei S80P_Shadeslayer Data 7 octombrie 2024 19:38:12
Problema Range minimum query Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 1, P = 1e4 + 1;

ifstream fin("infinitywar.in");
ofstream fout("infinitywar.out");
#define cin fin
#define cout fout
int n, q, p = 1, maxim;

//bitset<P> b[N];
vector<int> v[N];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    vector<pair<int, int>> qr(q + 1);
    vector<int> ans(q + 1);
    for(int i = 1; i <= n; i++){
        int k;
        cin >> k;
        for(int j = 1; j <= k; j++){
            int x;
            cin >> x;
            maxim = max(maxim, x);
            v[i].push_back(x);
        }
    }
    for(int i = 1; i <= q; i++){
        int l, r;
        cin >> l >> r;
        qr[i] = {l, r};
    }
    while(p <= maxim){

        vector<unsigned long long> b(n + 1);
        for(int i = 1; i <= n; i++){
            for(auto j : v[i]){
                if(p <= j && j <= p + 63){
                    b[i] = 1ULL * b[i] + (1ULL << (j - p));
                }
            }
            b[i] ^= b[i - 1];
        }
        for(int i = 1; i <= q; i++){
            unsigned long long nr = b[qr[i].second] ^ b[qr[i].first - 1];
            ans[i] += __builtin_popcountll(nr);
        }
        p++;
        p += 63;
    }
    for(int i = 1; i <= q; i++){
        cout << ans[i] << '\n';
    }
    //cout << 'a';
}