#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define int long long
struct Data{
long long x, y;
int sum;
Data(long long x, long long y, int sum):x(x), y(y), sum(sum){}
bool operator<(const Data&r)const{
return x < r.x || (x == r.x && y < r.y);
}
};
vector<Data> srt[70][70];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
auto len = [&](long long x){
return 64 - __builtin_clzll(x);
};
register int i, j;
// mt19937 gen(23523);
// uniform_int_distribution<long long> uid(1, (long long)1e18);
int n, q;
cin >> n >> q;
// n = q = 200000;
for(i = 0; i < n; ++i){
long long x, y;
int v;
cin >> x >> y >> v;
// x = uid(gen), y = uid(gen), v = uid(gen);
srt[len(x) - 1][len(y) - 1].push_back({x, y, v});
}
for(i = 0; i < 70; ++i){
for(j = 0; j < 70; ++j){
sort(srt[i][j].begin(), srt[i][j].end());
for(int k = 1; k < (int)srt[i][j].size(); ++k){
srt[i][j][k].sum += srt[i][j][k - 1].sum;
}
}
}
register int p1, p2;
register long long x, y;
register int ans;
register int lx, ly;
register long long yv;
for(int rep = 0; rep < q; ++rep){
cin >> x >> y;
yv = y;
lx = len(x) - 1, ly = len(y) - 1;
ans = 0;
for(i = lx; i >= 0; --i){
if(x >= (1 << (i + 1))) x -= 1 << i;
if(x >= (1 << (i + 1))) x -= 1 << i;
y = yv;
for(j = ly; j >= 0; --j){
if(y >= (1 << (j + 1))) y -= 1 << j;
if(y >= (1 << (j + 1))) y -= 1 << j;
if(!(int)srt[i][j].size()) continue;
p1 = lower_bound(srt[i][j].begin(), srt[i][j].end(), Data(x, y, -1)) - srt[i][j].begin();
p2 = lower_bound(srt[i][j].begin(), srt[i][j].end(), Data(x, y + 1, -1)) - srt[i][j].begin() - 1;
if(p1 <= p2){
ans += srt[i][j][p2].sum;
if(p1) ans -= srt[i][j][p1 - 1].sum;
}
}
}
cout << ans << '\n';
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:26:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
26 | register int i, j;
| ^
Main.cpp:26:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
26 | register int i, j;
| ^
Main.cpp:51:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
51 | register int p1, p2;
| ^~
Main.cpp:51:22: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
51 | register int p1, p2;
| ^~
Main.cpp:52:24: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
52 | register long long x, y;
| ^
Main.cpp:52:27: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
52 | register long long x, y;
| ^
Main.cpp:53:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
53 | register int ans;
| ^~~
Main.cpp:54:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
54 | register int lx, ly;
| ^~
Main.cpp:54:22: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
54 | register int lx, ly;
| ^~
Main.cpp:55:24: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
55 | register long long yv;
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2033 ms |
5856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
418 ms |
3648 KB |
Output is correct |
| 3 |
Correct |
399 ms |
3872 KB |
Output is correct |
| 4 |
Execution timed out |
4062 ms |
3964 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
