#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define pii pair <int, int>
// #define ordered_set tree<pair<pii,int>, null_type,less<pair<pii,int>>, rb_tree_tag,tree_order_statistics_node_update>
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pb push_back
#define ff first
#define ss second
const int N = 1e6;
int M = 0;
int n, q;
map<int,int> now1, now2, now3;
map<pii,int> num;
int pos[N], s[N], t[N], ans[N];
int x[N], y[N], z[N], ind[N];
int f[N][2];
void upd(int x, int y, int l = 1, int r = M, int idx = 1){
if (l == r){
num[{x, idx}]++;
return;
}
int md = (l+r)>>1;
if (md <= y) upd(x, y, l, md, idx<<1);
else upd(x, y, md+1, r, idx<<1|1);
num[{x, idx}] = num[{x, idx<<1}]+num[{x, idx<<1|1}];
}
int get(int x, int y, int l = 1, int r = M, int idx = 1){
if (l > y) return 0;
if (r <= y) return num[{x, idx}];
int md = (l+r)>>1;
return get(x, y, l, md, idx<<1)+get(x, y, md+1, r, idx<<1|1);
}
void add(int x, int y){
for (int i = x; i <= M; i += i&(-i)){
f[i][0]++;
upd(i, y);
}
for (int i = y; i <= M; i += i&(-i)){
f[i][1]++;
}
}
int count(int x, int y){
int cnt = 0;
for (int i = x; i > 0; i -= i&(-i)){
cnt += f[i][0];
// cnt -= get(i, y);
}
// if (x == 5 and y == 4) cout << "APA" << '\n';
for (int i = y; i > 0; i -= i&(-i)){
cnt += f[i][1];
}
return cnt;
}
int main ()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
set<int> dec1, dec2, dec3;
for (int i = 1; i <= n; i++){
cin >> s[i] >> t[i];
dec1.insert(s[i]);
dec2.insert(t[i]);
dec3.insert(s[i]+t[i]);
pos[i] = i;
}
for (int i = 1; i <= q; i++){
cin >> x[i] >> y[i] >> z[i];
dec1.insert(x[i]);
dec2.insert(y[i]);
dec3.insert(z[i]);
}
int T = 0;
for (auto i : dec1){
now1[i] = ++T;
}
M = T;
T = 0;
for (auto i : dec2){
now2[i] = ++T;
}
M = max(M, T);
T = 0;
for (auto i : dec3){
now3[i] = ++T;
}
// sort(pos+1,pos+n+1, [&](int x, int y){
// return (now3[s[x]+t[x]]) > (now3[s[y]+t[y]]);
// });
// add(4, 5);
// add(3, 7);
// add(1, 1);
// add(2, 2);
// cout << count(5, 8);
// cout << now3[115] << '\n';
for (int i = 1; i <= n; i++){
add(now1[s[i]], now2[t[i]]);
}
for (int i = 1; i <= q; i++){
x[i] = now1[x[i]];
y[i] = now2[y[i]];
z[i] = now3[z[i]];
cout << n-count(x[i]-1, y[i]-1) << '\n';
// ind[i] = i;
}
// sort(ind+1,ind+q+1, [&](int x, int y){
// return z[x] > z[y];
// });
// cout << now1[60] << " " << now2[60] << '\n';
// int l = 0;
// for (int i = 1; i <= q; i++){
// while(l < n and now3[s[pos[l+1]]+t[pos[l+1]]] >= z[ind[i]]){
// l++;
// add(now1[s[pos[l]]], now2[t[pos[l]]]);
// }
// // cout << l << " " << count(x[ind[i]]-1, y[ind[i]]-1) << ' ';
// // cout << x[ind[i]]-1 << " " << y[ind[i]]-1 << '\n';
// ans[ind[i]] = l-count(x[ind[i]]-1, y[ind[i]]-1);
// }
// for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3042 ms |
209608 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3042 ms |
209608 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
