Submission #1349696

#TimeUsernameProblemLanguageResultExecution timeMemory
1349696mishasimVera and Modern Art (CCO17_art)C++20
15 / 25
4094 ms13300 KiB
#include <bits/stdc++.h>
using namespace std;

struct HashPair {
    size_t operator()(const pair<long long,long long>& p) const {
        return hash<long long>()(p.first) ^
              (hash<long long>()(p.second) << 1);
    }
};

unordered_map<pair<long long,long long>, long long, HashPair> m[61][61];

vector<pair<int,int>> active;
bool used[61][61];

long long pw[61];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 0; i <= 60; i++) pw[i] = (1LL << i);

    long long n, q;
    cin >> n >> q;

    long long x, y, v;

    for (int i = 0; i < n; i++) {
        cin >> x >> y >> v;

        int lx = 63 - __builtin_clzll(x);
        int ly = 63 - __builtin_clzll(y);

        long long rx = x & (pw[lx] - 1);
        long long ry = y & (pw[ly] - 1);

        if (!used[lx][ly]) {
            used[lx][ly] = true;
            active.push_back({lx, ly});
        }

        m[lx][ly][{rx, ry}] += v;
    }

    while (q--) {
        cin >> x >> y;
        long long res = 0;

        for (auto [lx, ly] : active) {
            if (pw[lx] > x || pw[ly] > y) continue;

            long long rx = x & (pw[lx] - 1);
            long long ry = y & (pw[ly] - 1);

            auto it = m[lx][ly].find({rx, ry});
            if (it != m[lx][ly].end())
                res += it->second;
        }

        cout << res << '\n';
    }
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...